QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94399#6192. Interval ProblemHOLIC#WA 75ms23576kbC++202.0kb2023-04-05 19:59:562023-04-05 19:59:58

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:59:58]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:23576kb
  • [2023-04-05 19:59:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
#define ll long long
#define endl "\n"
struct node{
    int l, r, id;
} a[N];
int fa[N], n, m, l1[N], r1[N], num[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);
    }
    for(int i = 1; i <= n; i ++) {
        num[i] = n - R.query(1, l1[i]) - L.query(r1[i], m) - 1;
    }
    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;
    int Num = 1;
    for(int i = 1; i < b.size(); i ++) {
        if(b[i - 1].r <= b[i].l) sum = 0, Num = b[i - 1].r + 1;
        int num1 = R.query(Num, b[i].l);
        sum = sum + 2 * num1;
        ans[b[i].id] += sum;
    }
    sum = 0;
    Num = m;
    for(int i = (int)(b.size()) - 2; i >= 0; i --) {
        if(b[i + 1].l >= b[i].r) sum = 0, Num = b[i + 1].l - 1;
        int num1 = L.query(b[i].r, Num);
        sum = sum + 2 * num1;
        ans[b[i].id] += sum;
    }
    for(int i = 1; i <= n; i ++) {
        val[i] = ans[fa[i]] + num[i] + (num[fa[i]] - num[i]) * 2;
    }
    for(int i = 1; i <= n; i ++)
        cout << val[i] << 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: 2ms
memory: 17776kb

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
Wrong Answer
time: 75ms
memory: 23576kb

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:

11
20
21
6
16
37
2
1
1
33
5
0
39
22
6
11
2
17
14
8
2
12
0
1
0
2
48
50
50
6
4
0
30
21
20
11
35
10
5
9
1
16
16
21
8
1
2
58
16
13
28
12
4
26
2
48
0
0
33
20
0
36
4
11
18
20
26
12
2
4
0
51
11
0
1
6
84
7
1
23
3
6
1
57
7
29
16
12
45
58
4
10
27
30
1
0
4
4
0
1
8
3
1
20
55
23
61
5
14
45
73
0
0
0
34
0
23
21
7
...

result:

wrong answer 1st numbers differ - expected: '12', found: '11'