3. 星星
题目ID：2103 必做题100分
最新提交：
Time Limit Exceeded
30 分
历史最高：
Time Limit Exceeded
30 分
时间限制: 100ms
空间限制: 524288kB
题目描述
天空上有很多的星星，非常的漂亮。有一天，聪聪看到如此多美丽的星星，便被吸引了。聪聪是个很认真的小朋友，所以他想把这些美丽的星星都记录下来。但是，星星实在太多了，聪聪实在分不清，所以聪聪想出了一个办法来给星星们分类。
聪聪把天空看成了一张地图，并且细心的以东西和南北为坐标轴，为天空建立了一个坐标系。因此，现在每颗星星都有了自己独特的坐标。聪聪给每颗星星一个等级，表示在这颗星星西南边的星星个数。
虽然聪聪有了给星星分类的方式，但是要给如此多的星星分类，实在是个困难的工作，因此聪聪想请厉害的你帮助他。
输入格式：
第一行是一个n（1<=n<=15000）表示天空中的星星个数。
以下每行以东西坐标，和南北坐标描述一颗星星。
输出格式：
需要输出n行，第一行代表等级为0的星星个数，第二行代表等级为1的星星个数，以此类推，第n行代表等级为n-1的星星的个数
样例输入：
5 1 1 5 1 7 1 3 3 5 5
样例输出：
1 2 1 1 0
数据范围：
对于30%的数据，n<=5000
对于70%的数据，n<=10000
对于全部数据，n<=15000 0<=x,y<=32000
时间限制：
1S
空间限制：
512M
提示：
remove!!!
我的代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL Y = 32000;
const LL X = 15000;
struct Star {
LL x, y, index;
};
LL n;
Star stars[X];
LL tre[Y + 1];
void update(LL x, LL k) {
while (x <= Y) {
tre[x] += k;
x += x & -x;
}
}
LL query(LL x) {
LL sum = 0;
while (x > 0) {
sum += tre[x];
x -= x & -x;
}
return sum;
}
int main(void)
{
cin >> n;
for (LL i = 0; i < n; ++i) {
cin >> stars[i].x >> stars[i].y;
stars[i].index = i;
}
sort(stars, stars + n, [](const Star& a, const Star& b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
});
vector<LL> cnt(n, 0);
for (LL i = 0; i < n; ++i) {
LL y = stars[i].y;
LL count = query(y);
cnt[count]++;
update(y, 1);
}
for (LL i = 0; i < n; ++i) {
cout << cnt[i] << '\n';
}
return 0;
}
TLE30求调