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;
}

Download