[Educational Codeforces Round 10D] [트 리 배열] Nested Segments 각 라인 내부 에 몇 개의 라인 이 있 습 니까?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.
Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Output
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
Examples
input
4
1 8
2 3
4 7
5 6
output
3
0
1
0
input
3
3 4
1 5
2 6
output
0
1
1
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 2e5 + 10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int n;
int b[N + N];
int l[N], r[N];
map<int, int>mop;
map<int, int>::iterator it;
struct A
{
int x, y, o;
bool operator < (const A& b)const
{
if (x != b.x)return x < b.x;
return y < b.y;
}
}a[N];
int id;
void add(int x, int val)
{
for (x; x <= id; x += (x&-x))
{
b[x] += val;
}
}
int check(int x)
{
int tmp = 0;
for (; x; x -= (x&-x))
{
tmp += b[x];
}
return tmp;
}
int ans[N];
int main()
{
while (~scanf("%d", &n))
{
mop.clear();
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &l[i], &r[i]);
mop[l[i]] = 0;
mop[r[i]] = 0;
}
id = 0;
for (it = mop.begin(); it != mop.end(); ++it)
{
it->second = ++id;
b[id] = 0;
}
for (int i = 1; i <= n; ++i)
{
int x = mop[l[i]];
int y = mop[r[i]];
a[i].x = x;
a[i].y = y;
a[i].o = i;
add(y, 1);
}
sort(a + 1, a + n + 1);
int p = 1;
for (int i = 1; i <= n; ++i)
{
while (p <= n&&a[p].x < a[i].x)
{
add(a[p].y, -1);
++p;
}
ans[a[p].o] = check(a[p].y) - 1;
}
for (int i = 1; i <= n; ++i)printf("%d
", ans[i]);
}
return 0;
}
/*
【 】
n(2e5) , [-1e9,1e9]
( )
【 】
【 】
。
。 <= 。
【 && 】
O(nlogn)
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.