CRATE - Coder Rating
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 100001
#define N 300000
struct contestant {
int p1, p2, id;
bool operator < (const contestant &o) const {
return p1 < o.p1 || p1 == o.p1 && p2 < o.p2;
}
bool operator == (const contestant &o) const {
return p1 == o.p1 && p2 == o.p2;
}
} a[N];
int answer[N], bit[MAX+1], n;
void enter() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d%d",&a[i].p1,&a[i].p2);
++a[i].p1; ++a[i].p2; a[i].id = i;
}
}
void add(int idx, int v) {
for(; idx <= MAX; idx += idx & -idx) bit[idx] += v;
}
int sum(int idx) {
int res = 0;
for(; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
void solve() {
sort(a, a+n);
for(int i = 0; i < n; ++i) {
if(i != 0 && a[i] == a[i-1]) {
answer[a[i].id] = answer[a[i-1].id];
} else answer[a[i].id] = sum(a[i].p2);
add(a[i].p2, 1);
}
for(int i = 0; i < n; ++i) printf("%d\n", answer[i]);
}
int main() {
enter();
solve();
return 0;
}