// Problem 1008: 2D dominance counting (n = 1e7)
// Counting sort by x -> gather contiguous ysort/idxsort/xsort -> Fenwick sweep.
#include <cstring>
static int cnt[10000000];
static int order[10000000];
static unsigned ysort[10000000];
static int idxsort[10000000];
static unsigned xsort[10000000];
static unsigned tree[10000001];
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
// counting sort by x
for (int i = 0; i < n; ++i) cnt[x[i]]++;
for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; ++i) order[--cnt[x[i]]] = i;
// gather contiguous arrays (makes sweep's y/x/idx reads sequential)
for (int k = 0; k < n; ++k) {
int ii = order[k];
ysort[k] = y[ii];
idxsort[k] = ii;
xsort[k] = x[ii];
}
// sweep in x order; within one x-bucket: query all, then update all
int k = 0;
while (k < n) {
unsigned cur_x = xsort[k];
int kk = k + 1;
while (kk < n && xsort[kk] == cur_x) kk++;
for (int t = k; t < kk; ++t) {
unsigned s = 0;
for (unsigned j = ysort[t]; j; j &= j - 1) s += tree[j];
out[idxsort[t]] = s;
}
for (int t = k; t < kk; ++t) {
for (unsigned j = ysort[t] + 1; j <= (unsigned)n; j += j & -j) tree[j]++;
}
k = kk;
}
}