QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852777#8704. 排队__zyx__0 86ms6448kbC++141.5kb2025-01-11 13:57:032025-01-11 13:57:04

Judging History

This is the latest submission verdict.

  • [2025-01-11 13:57:04]
  • Judged
  • Verdict: 0
  • Time: 86ms
  • Memory: 6448kb
Show
  • [2025-01-11 13:57:03]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct node {
	int w, ls, rs, rd, siz, fa;
}t[N];
#define ls(k) t[k].ls
#define rs(k) t[k].rs
void pushup(int k) {
	t[k].siz = t[ls(k)].siz + t[rs(k)].siz + 1;
	t[ls(k)].fa = t[rs(k)].fa = k;
}
void split(int k, int w, int &x, int &y) {
	if (!k) return x = y = 0, void();
	if (t[ls(k)].siz >= w) y = k, split(ls(k), w, x, ls(y)), pushup(y);
	else x = k, split(rs(k), w - t[ls(k)].siz - 1, rs(x), y), pushup(x); 
}
int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].rd > t[y].rd) return rs(x) = merge(rs(x), y), pushup(x), x;
	else return ls(y) = merge(x, ls(y)), pushup(y), y;
} 
int ts, rt, fx, fy, fz;
mt19937 Rand(2347); 
int newnode() {
	return ts++, t[ts] = {ts, 0, 0, Rand(), 1, 0}, ts;
}
int erase(int pos) {
	split(rt, pos, fx, fy);
	split(fx, pos - 1, fx, fz);
	return rt = merge(fx, fy), fz;
}
int rnk(int x) {
	int res = t[ls(x)].siz;
	while (x) {
		if (t[t[x].fa].rs == x) 
			res += t[ls(t[x].fa)].siz;
		res++, x = t[x].fa;
	}
	return res;
}
void insert(int x, int pos) {
	split(rt, pos, fx, fy);
	rt = merge(merge(fx, x), fy);
} 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int sub, n; cin >> sub >> n;
	while (n--) {
		int op, x, y; cin >> op >> x;
		if (op == 1) insert(newnode(), rnk(x));
		else if (op == 2) 
			cin >> y, erase(rnk(x)), insert(x, rnk(y));
		else cout << rnk(x) << '\n';
	}
	return 0; 
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

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

output:

result:

Subtask #2:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 86ms
memory: 6448kb

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
4
4
3
6
6
7
7
6
3
7
7
9
14
8
9
8
18
18
9
7
12
8
8
20
21
9
18
8
8
20
13
9
7
22
7
20
26
27
22
28
31
7
4
22
25
22
22
13
38
7
26
39
39
9
28
40
40
13
37
28
20
24
37
9
29
43
31
39
23
29
13
20
47
17
29
22
52
9
22
52
53
4
31
4
56
13
44
31
62
8
9
13
50
22
48
45
22
66
29
8
8
9
7
63
66
44
64
64
17
...

result:

wrong answer 7th lines differ - expected: '3', found: '4'

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 80ms
memory: 5996kb

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
2
7
6
10
6
10
7
6
7
9
11
11
3
4
3
9
7
12
12
6
4
9
9
12
6
15
14
10
9
12
9
10
12
7
4
9
12
12
18
4
17
16
16
7
6
6
13
16
7
6
9
4
15
6
14
22
7
21
14
6
19
9
14
16
7
15
21
7
25
13
25
25
14
6
21
19
26
26
19
14
16
26
22
15
16
23
9
9
16
14
29
10
15
30
27
15
10
4
23
25
34
25
31
8
15
27
28
30
43...

result:

wrong answer 9th lines differ - expected: '1', found: '2'

Subtask #4:

score: 0
Memory Limit Exceeded

Test #35:

score: 0
Memory Limit Exceeded

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:

result:

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2025-02-08 12:56:02 | OpenSource Project