1028. Stars @ Timus Online Judge. (with Fenwick Tree)

Timus-1028-BIT.cpp

#include <iostream>
#include <vector>
using namespace std;

#define MAX 32111

int tree[MAX+1];

int read(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= (idx & -idx))
        sum += tree[idx];
    return sum;
}

int update(int idx, int val) {
    for (; idx <= MAX; idx += (idx & -idx))
        tree[idx] += val;
}

int rsq(int l, int r) { return read(r) - read(l - 1); }

int main() {
    int N;
    cin >> N;
    vector<int> ans(N + 1, 0);
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        ++ans[read(x + 1)];
        update(x + 1, 1);
    }
    for (int i = 0; i < N; i++)
        cout << ans[i] << endl;
    return 0;
}