QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94389#6192. Interval ProblemHOLIC#TL 5ms13576kbC++202.1kb2023-04-05 19:18:352023-04-05 19:18:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 19:18:37]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:13576kb
  • [2023-04-05 19:18:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
#define ll long long
struct node{
    int l, r, id;
} a[N];
int fa[N], n, m, l1[N], r1[N];
ll ans[N], val[N];
struct BIT{
    int c[N];
    void add(int x) {
        for(; x <= m; x += x & -x) c[x] ++;
    }
    int query(int x) {
        int ans = 0;
        for(; x; x -= x & -x) ans += c[x];
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}L, R;
void work() {
    cin >> n;
    m = 2 * n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
        l1[i] = a[i].l;
        r1[i] = a[i].r;
        R.add(a[i].r);
        L.add(a[i].l);
    }
    sort(a + 1, a + n + 1, [&](node x, node y) {
       if(x.l != y.l) return x.l < y.l;
       return x.r > y.r;
    });
    int maxnr = -1, F = 0;
    vector<node> b;
    for(int i = 1; i <= n; i ++) {
        if(maxnr < a[i].r) {
            F = a[i].id;
            b.push_back(a[i]);
            maxnr = a[i].r;
        }
        fa[a[i].id] = F;
    }
    ll sum = 0;
    for(int i = 1; i < b.size(); i ++) {
        int num1 = R.query(1, b[i].l - 1);
        sum = sum + 2 * num1;
        if(b[i - 1].r < b[i].l) sum = 0;
        ans[b[i].id] += sum;
    }
    sum = 0;
    for(int i = (int)b.size() - 2; i >= 0; i --) {
        int num1 = L.query(b[i].r + 1, m);
        sum = sum + 2 * num1;
        if(b[i + 1].l > b[i].r) sum = 0;
        ans[b[i].id] += sum;
    }
    for(int i = 1; i <= n; i ++) {
        int l = l1[i];
        int r = r1[i];
        int pa = fa[i];
        int pl = l1[pa];
        int pr = r1[pa];
        int num1 = n - R.query(1, l - 1) - L.query(r + 1, n) - 1;
        int num2 = n - R.query(1, pl - 1) - L.query(pr + 1, n) - 1;
        val[i] = ans[pa] + num1 + (num2 - num1) * 2;
    }
    for(int i = 1; i <= n; i ++)
        cout << val[i] - 1<< endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    while(Case --) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 13576kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

7
5
4
5
5

result:

ok 5 number(s): "7 5 4 5 5"

Test #2:

score: -100
Time Limit Exceeded

input:

200000
342504 342505
248314 248317
259328 259334
234817 234821
225726 225732
371424 371425
260562 260565
34752 34753
132098 132100
262130 262134
7254 7255
228491 228492
43488 43492
188408 188410
11691 11692
350334 350335
327350 327352
360684 360685
182051 182052
72131 72135
194666 194668
61303 61313...

output:

157499
1093226
877967
430352
499992
1957065
499994
99999
232095
1051419
885483
99998
1569487
711576
499994
450333
100000
178619
682034
427864
305330
622584
99998
182671
99998
100000
1268290
1658528
558092
1008724
124170
99998
1292898
358267
122416
153865
1488313
125070
499995
899979
99999
267208
118...

result: