QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850054#8704. 排队hhoppitree0 0ms3896kbC++171.7kb2025-01-09 20:01:082025-01-09 20:01:11

Judging History

This is the latest submission verdict.

  • [2025-01-09 20:01:11]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 3896kb
Show
  • [2025-01-09 20:01:08]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

mt19937 rnd;

struct Node {
    int ls, rs, fa, mn, siz;
    unsigned int key;
} p[N];

int rt;

void pushup(int k) {
    p[k].mn = min({p[p[k].ls].mn, p[p[k].rs].mn, k});
    p[k].siz = p[p[k].ls].siz + p[p[k].rs].siz + 1;
}

void split(int k, int x, int &a, int &b) {
    if (!k) {
        a = b = 0;
        return;
    }
    if (p[p[k].ls].siz + 1 <= x) {
        a = k, p[p[k].rs].fa = 0, split(p[k].rs, x - (p[p[x].ls].siz + 1), p[a].rs, b);
        if (p[k].rs) p[p[k].rs].fa = k;
    } else {
        b = k, p[p[k].ls].fa = 0, split(p[k].ls, x, a, p[b].ls);
        if (p[k].ls) p[p[k].ls].fa = k;
    }
    pushup(k);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (p[x].key < p[y].key) {
        p[x].rs = merge(p[x].rs, y), p[p[x].rs].fa = x, pushup(x);
        return x;
    }
    p[y].ls = merge(x, p[y].ls), p[p[y].ls].fa = y, pushup(y);
    return y;
}

int rnk(int x) {
    int res = p[p[x].ls].siz + 1;
    while (x != rt) {
        if (p[p[x].fa].rs == x) res += p[p[x].fa].ls + 1;
        x = p[x].fa;
    }
    return res;
}

signed main() {
    int n, m = 0; scanf("%*d%d", &n);
    p[0].mn = n + 1;
    for (int i = 1; i <= n; ++i) {
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) {
            ++m, p[m].mn = x, p[m].siz = 1, p[m].key = rnd();
            if (x) x = rnk(x);
            int a, b;
            split(rt, x, a, b);
            rt = merge(merge(a, m), b);
        } else if (opt == 2) {
            int y; scanf("%d", &y);
        } else {
            printf("%d\n", rnk(x));
        }
    }
    return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3896kb

input:

0 8
1 0
1 1
1 2
3 2
2 2 0
3 1
3 2
3 3

output:

2
1
2
3

result:

wrong answer 2nd lines differ - expected: '3', found: '1'

Subtask #2:

score: 0
Runtime Error

Test #5:

score: 0
Runtime Error

input:

1 298913
1 0
3 1
3 1
3 1
3 1
3 1
1 0
1 0
3 3
1 2
1 2
3 5
3 5
1 1
1 3
1 4
3 3
1 3
1 6
3 7
3 2
3 5
3 8
3 2
1 8
3 3
1 4
3 2
3 7
1 3
3 4
1 10
3 14
3 13
1 12
3 4
1 8
1 15
1 16
3 9
3 14
3 10
3 8
3 7
1 16
1 15
3 16
3 13
1 19
3 13
3 1
3 14
1 18
1 22
3 8
1 17
3 18
3 9
1 18
3 9
3 1
1 20
3 11
3 5
3 2
3 22
1 22...

output:

1
1
1
1
1
1
3
3
1
5
4
5
7
4
1
4
5
4
16
2
4
5
16
6
7
6
28
2
2
5
16
7
8
5
5
5
20
14
5
32
5
22
27
9
25
26
16
6
1
25
37
29
8
20
27
5
38
16
16
15
54
16
27
7
9
13
9
28
26
15
31
6
32
29
5
54
22
9
100
45
54
8
201
7
22
56
56
1
32
1
201
7
27
13
52
2
15
28
54
22
60
27
22
149
31
2
2
16
6
56
57
123
101
56
45
31
...

result:

Subtask #3:

score: 0
Runtime Error

Test #20:

score: 0
Runtime Error

input:

2 298235
1 0
1 1
3 2
1 0
1 3
3 4
3 3
3 3
3 2
3 4
3 2
3 3
1 2
3 3
1 4
1 2
1 1
3 5
3 8
1 5
1 9
3 10
3 8
3 10
3 5
3 8
3 5
1 2
1 9
3 5
3 7
3 12
3 3
1 6
3 4
3 3
3 11
3 8
3 9
3 7
3 6
3 4
1 12
1 11
3 13
3 13
1 11
3 16
3 6
3 14
3 9
3 5
3 13
1 9
1 17
3 16
3 13
3 5
3 15
3 8
3 4
3 13
1 18
3 15
3 16
3 19
3 4
1 ...

output:

2
2
1
1
4
2
4
1
1
8
5
5
6
5
9
6
9
4
10
3
1
2
1
11
8
5
10
5
2
9
9
5
5
4
22
4
9
5
9
4
6
10
2
9
6
5
25
2
23
23
23
12
5
5
6
8
12
6
9
2
9
6
22
25
16
42
17
6
4
9
22
23
12
9
42
16
41
5
41
41
17
5
24
23
43
41
4
17
8
43
24
9
23
26
15
15
23
22
7
16
17
7
43
17
9
1
55
74
7
55
23
33
17
56
56
58
76
46
105
9
23
16...

result:

Subtask #4:

score: 0
Runtime Error

Test #35:

score: 0
Runtime Error

input:

3 299743
1 0
1 1
3 1
1 2
3 2
1 0
3 3
3 2
3 1
3 2
2 2 1
3 3
3 3
3 4
3 1
3 2
3 2
2 1 0
3 2
3 1
3 1
1 0
3 2
1 2
1 1
3 2
2 5 2
1 6
1 0
2 5 2
1 7
3 8
3 5
3 5
2 7 5
2 9 4
3 5
3 8
2 6 2
2 3 0
2 2 0
1 1
2 3 1
1 8
2 7 0
3 3
1 12
2 13 9
1 5
2 2 1
2 14 13
1 12
2 1 0
2 12 10
2 15 12
1 0
1 6
3 6
2 3 2
2 17 6
3 4...

output:

1
2
3
3
2
3
3
3
1
2
3
3
3
2
2
4
5
15
2
2
2
15
13
27
12
3
11
7
7
47
42
16
26
16
16
13
30
12
11
46
7
32
22
42
50
42
42
38
49
51
11
83
39
55
19
37
4
4
82
36
68
4
52
18
88
77
78
79
82
104
39
90
84
45
52
83
28
106
57
21
54
2
250
96
140
145
57
175
82
105
249
106
46
258
2
71
71
105
46
123
89
90
332
318
112...

result:

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2025-02-08 16:02:20 | 开源项目