排名

题目描述

sys 参加了一场 AI 算法大赛，大赛要求参赛者提供一个程序，后台的评测系统会使用相同的数据对所有提交程序进行评测，通过程序的运行时间与内存占用来衡量一个算法的好坏。

比赛的成绩计算方法为，给每一个程序进行打分，对于一个程序来说，该程序的得分为：运行时间与内存占用均小于等于该程序的程序的数量。

现在需要你来计算，成绩为 $0,1,\dots n-1$ 的程序的数量分别为多少。

输入格式

第一行一个整数 $N$，表示程序的数目；
接下来 $N$ 行给出每个程序的运行时间与内存占用，用两个空格隔开的整数表示；
不会有两个程序的运行时间与内存占用均相同。

输出格式

$n$ 行，每行一个整数，分别是得分为 $0$，$1$，$2$，$\dots$，$n-1$ 的程序的数目。

样例

输入

5
1 1
5 1
7 1
3 3
5 5

输出

1
2
1
1
0

样例解释

得分为 $0$ 的程序为 $(1\ 1)$

得分为 $1$ 的程序为 $(5\ 1) \ (3 \ 3)$

得分为 $2$ 的程序为 $(7\ 1)$

得分为 $3$ 的程序为 $(5\ 5)$

得分为 $4$ 的程序为：无

数据范围

对于全部数据，$1\le n\le 10^6$，$0\le 运行时间,内存占用 \le 10^6$。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000003
int bit[MAXN + 1], n, t, m, ans[MAXN];

inline int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

inline void add(int i, const int& x) {
    while (i <= MAXN) {  // 注意这里由于题目的特点和普通的数字数组不一样
        bit[i] += x;
        i += i & -i;
    }
}

struct cx {
    int t, m;
    cx(const int& t = 0, const int& m = 0) : t(t), m(m) {}
    bool operator<(const cx& c) {
        return t < c.t || (t == c.t && m < c.m);
    }
} tcx;

vector<cx> v;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &t, &m), v.emplace_back(++t, ++m);
    sort(v.begin(), v.end());
    for (auto& i : v)
        ans[sum(i.m)]++, add(i.m, 1);
    for (int i = 0; i < n; ++i)
        printf("%d\n", ans[i]);
}