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

Timus-1028.cpp

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

#define MAX 32111

int st[4 * MAX], N;

int query(int v, int l, int r, int i, int j) {
    if (i > r || j < l) return 0;
    if (l >= i && r <= j) return st[v];
    int nL = v << 1, nR = nL + 1, mid = (l + r) / 2;
    int r1 = query(nL, l, mid, i, j);
    int r2 = query(nR, mid + 1, r, i, j);
    return r1 + r2;
}

int query(int i, int j) {
    return query(1, 0, MAX - 1, i, j);
}

void update(int v, int l, int r, int pos, int val) {
    if (pos < l || pos > r) return;
    if (l == r) st[v] += val;
    else {
        int nL = v << 1, nR = nL + 1, mid = (l + r) / 2;
        if (pos <= mid) update(nL, l, mid, pos, val);
        else update(nR, mid + 1, r, pos, val);
        st[v] = st[nL] + st[nR];
    }
}

void update(int pos, int val) {
    update(1, 0, MAX - 1, pos, val);
}

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