为什么洛谷在线IDE上过了?
查看原帖
为什么洛谷在线IDE上过了?
360214
nalemy楼主2021/4/1 13:14

rt,为什么在洛谷IDE上把第一个测试点过了但是在题目里面就全都RE?

#include<iostream>
#include<algorithm>
#define N 1000010
using namespace std;

int k, tr[N], f[N];
struct point {
    int a, b, c, cnt, ans;
} d[N];
bool inline by_a(point a, point b) {
    if (a.a != b.a) return a.a < b.a;
    if (a.b != b.b) return a.b < b.b;
    if (a.c != b.c) return a.c < b.c;
    return false;
}
bool inline by_b(point a, point b) {
    if (a.b != b.b) return a.b < b.b;
    if (a.c != b.c) return a.c < b.c;
    if (a.a != b.a) return a.a < b.a;
    return false;
}
bool inline equal(point a, point b) {
    return a.a == b.a && a.b == b.b && a.c == b.c;
}
int lowbit(int x) { return x & -x; }
void upd(int x, int v) {
    while (x <= k)
        tr[x] += v, x += lowbit(x);
}
int qry(int x) {
    int sm = 0;
    while (x)
        sm += tr[x], x -= lowbit(x);
    return sm;
}
void CDQ(int l, int r) {  // 左闭右开 
    if (r - l == 1) {
        d[l].ans += d[l].cnt - 1;
        return;
    }
    int mid = l + r >> 1, j = l;
    CDQ(l, mid), CDQ(mid, r);
    sort(d+l, d+mid, by_b);
    sort(d+mid, d+r, by_b);
    for (int i=mid; i<r; i++) {
         while (j<mid && d[j].b <= d[i].b)
            upd(d[j].c, d[j].cnt), j++;
        d[i].ans += qry(d[i].c);
    }
    for (int i=l; i<j; i++)
        upd(d[i].c, -d[i].cnt);
}
int main() {
    int n, tot; cin >> n >> k;
    for (int i=0; i<n; i++)
        scanf("%d %d %d", &d[i].a, &d[i].b, &d[i].c), d[i].ans = 1;
    sort(d, d+n, by_a);
    for (int i=0; i<n; i++)
        if (i && equal(d[i], d[i-1])) d[tot-1].cnt++;
        else d[tot] = d[i], d[tot++].cnt = 1;
    CDQ(0, tot);
    sort(d, d+tot, by_a);
    for (int i=0; i<tot; i++)
        f[d[i].ans] += d[i].cnt;
    for (int i=1; i<=n; i++)
        cout << f[i] << endl; 
    return 0;
}

2021/4/1 13:14
加载中...