QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94396#6192. Interval ProblemHOLIC#WA 77ms19468kbC++202.0kb2023-04-05 19:41:362023-04-05 19:41:39

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:41:39]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:19468kb
  • [2023-04-05 19:41:36]
  • 提交

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] - 1) - L.query(r1[i] + 1, 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 - 1);
        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 + 1, 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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 17716kb

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: 77ms
memory: 19468kb

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'