QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852432#8704. 排队ddxrS19 512ms23336kbC++144.8kb2025-01-11 11:49:352025-01-11 11:49:36

Judging History

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

  • [2025-01-11 11:49:36]
  • 评测
  • 测评结果：19
  • 用时：512ms
  • 内存：23336kb
查看
  • [2025-01-11 11:49:35]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e6 + 5;
const ll mod = 998244353;
mt19937 rnd(time(NULL));
int C, n, id = 1;
int son[N][2], key[N], val[N], val_[N], rnk[N], fa[N], siz[N];
void pushup(int p) {
	siz[p] = siz[son[p][0]] + 1 + siz[son[p][1]];
	if(son[p][0]) fa[son[p][0]] = p; if(son[p][1]) fa[son[p][1]] = p;
	val[p] = min({val[son[p][0]], key[p], val[son[p][1]]});
	val_[p] = max({val_[son[p][0]], key[p], val_[son[p][1]]});
}
int merge(int rt1, int rt2) {
	if(!rt1 || !rt2) return rt1 | rt2;
	if(rnk[rt1] < rnk[rt2]) {
		son[rt1][1] = merge(son[rt1][1], rt2);
		pushup(rt1);
		return rt1;
	} else {
		son[rt2][0] = merge(rt1, son[rt2][0]);
		pushup(rt2);
		return rt2;
	}
}
pair<int, int> split(int rt, int y) {
	pair<int, int> ans = {0, 0};
	if(!rt) return ans;
	if(siz[son[rt][0]] < y) {
		fa[son[rt][1]] = 0;
		ans = split(son[rt][1], y - siz[son[rt][0]] - 1);
		son[rt][1] = ans.first;
		ans.first = rt;
	} else {
		fa[son[rt][0]] = 0;
		ans = split(son[rt][0], y);
		son[rt][0] = ans.second;
		ans.second = rt;
	}
	pushup(rt);
	return ans;
}
int getrot(int x) {while(fa[x]) x = fa[x]; return x;}
int getsiz(int x) {int ans = 0, p = -1; while(x) {if(p != son[x][0]) ans += siz[son[x][0]] + 1; p = x, x = fa[x];} return ans;}
int Findlst(int x, int y) {
	if(val[son[x][0]] < y) return Findlst(son[x][0], y);
	else if(key[x] < y) return x;
	else if(val[son[x][1]] < y) return Findlst(son[x][1], y);
	return -1;
}
int getlst(int x) {//找到 x 后面第一个小于 x 的数
	int sz = getsiz(x); pair<int, int> tmp = split(getrot(x), sz - 1);
	int lst = Findlst(tmp.second, x);
	merge(tmp.first, tmp.second);
	return lst;
}
int Findfir(int x, int y) {
	if(val_[son[x][1]] > y) return Findfir(son[x][1], y);
	else if(key[x] > y) return x;
	else if(val_[son[x][0]] > y) return Findfir(son[x][0], y);
	return -1;
}
int getfir(int x) {//找到 x 前面最后一个大于 x 的数
	int sz = getsiz(x); pair<int, int> tmp = split(getrot(x), sz);
	int fir = Findfir(tmp.first, x);
	merge(tmp.first, tmp.second);
	return fir;
}
void print(int p) {
	if(!p) return;
	print(son[p][0]), cout<<p - 1<<' ', print(son[p][1]);
}
int main() {
#ifdef ddxrS
	freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>C>>n;
	val[0] = 0x3f3f3f3f, val_[0] = 0xf3f3f3f3;
	key[1] = val[1] = val_[1] = 0, rnk[1] = rnd(), son[1][0] = son[1][1] = 0, siz[1] = 1;
	while(n--) {
		int opt, x, y;
		cin>>opt;
		if(opt == 1) {
			cin>>x; x++;
			int siz = getsiz(x);
			id++, key[id] = val[id] = val_[id] = id, rnk[id] = rnd(), son[id][0] = son[id][1] = 0, ::siz[id] = 1;
			pair<int, int> tmp = split(getrot(x), siz);
			merge(merge(tmp.first, id), tmp.second);
		} else if(opt == 2) {
			cin>>x>>y; x++, y++;
			int lst = getlst(x), fir = getfir(x);
			if(lst == -1) {
				pair<int, int> tmpl = split(getrot(y), getsiz(y));
				if(fir == -1) {
					pair<int, int> tmpr = split(tmpl.second, getsiz(x) - 1);
					merge(tmpl.first, merge(tmpr.second, tmpr.first));
				} else {
					pair<int, int> tmpm = split(tmpl.second, getsiz(fir));
					pair<int, int> tmpr = split(tmpm.second, getsiz(x) - 1);
					merge(tmpl.first, merge(tmpm.first, merge(tmpr.second, tmpr.first)));
				}
			} else {
				// print(getrot(x)), cout<<'\n';
				pair<int, int> tmpL = split(getrot(x), getsiz(x) - 1);
				pair<int, int> tmpR = split(tmpL.second, getsiz(lst) - 1);
				merge(tmpL.first, merge(tmpR.second, tmpR.first));
				// print(getrot(x)), cout<<'\n';
				lst = getlst(x), fir = getfir(x);
				if(lst == -1) {
					pair<int, int> tmpl = split(getrot(y), getsiz(y));
					if(fir == -1) {
						pair<int, int> tmpr = split(tmpl.second, getsiz(x) - 1);
						merge(tmpl.first, merge(tmpr.second, tmpr.first));
					} else {
						pair<int, int> tmpm = split(tmpl.second, getsiz(fir));
						pair<int, int> tmpr = split(tmpm.second, getsiz(x) - 1);
						merge(tmpl.first, merge(tmpm.first, merge(tmpr.second, tmpr.first)));
					}
				} else {
					pair<int, int> tmpl = split(getrot(y), getsiz(y));
					if(fir == -1) {
						pair<int, int> tmpm = split(tmpl.second, getsiz(x) - 1);
						pair<int, int> tmpr = split(tmpm.second, getsiz(lst) - 1);
						merge(tmpl.first, merge(tmpr.first, merge(tmpm.first, tmpr.second))); 
					} else {
						pair<int, int> tmpml = split(tmpl.second, getsiz(x) - 1);
						pair<int, int> tmpmr = split(tmpml.first, getsiz(fir));
						pair<int, int> tmpr = split(tmpml.second, getsiz(lst) - 1);
						merge(tmpl.first, merge(tmpr.first, merge(tmpr.first, merge(tmpmr.second, tmpr.second)))); 
					}
				}
			}
		} else if(opt == 3) cin>>x, cout<<getsiz(x + 1) - 1<<'\n';
		// print(getrot(1)), cout<<'\n';
	}
	cerr<<clock() * 1.0 / CLOCKS_PER_SEC<<'\n';
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 0ms
memory: 14172kb

input:

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

output:

2
3
1
2

result:

ok 4 lines

Test #2:

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

input:

0 485
1 0
2 1 0
2 1 0
3 1
3 1
1 0
1 1
3 3
2 3 2
2 2 1
2 2 1
2 2 0
3 1
3 1
3 1
1 0
2 3 0
1 2
3 3
1 3
2 3 2
1 1
2 2 0
1 3
2 3 0
2 1 0
1 1
2 8 6
2 3 0
3 3
2 4 1
1 4
3 2
1 0
1 5
1 4
2 3 2
2 7 4
3 5
1 7
1 8
2 7 5
3 14
3 2
2 6 2
3 13
1 0
3 11
1 13
3 1
3 4
1 4
2 15 0
2 15 9
2 17 16
3 13
1 17
2 17 12
3 3
3 ...

output:

1
1
3
3
3
3
2
7
4
5
15
4
9
2
3
9
12
8
19
9
5
8
14
20
25
3
11
16
18
35
34
28
5
8
34
15
18
38
21
27
29
45
23
32
52
1
48
50
12
25
35
66
60
63
32
60
31
40
34
18
48
45
19
8
77
76
53
59
41
66
12
49
44
34
33
59
40
75
38
57
85
78
13
74
55
71
8
31
27
49
90
3
50
31
21
54
58
88
85
47
88
102
73
48
25
90
27
38
6...

result:

wrong answer 8th lines differ - expected: '2', found: '7'

Subtask #2:

score: 19
Accepted

Test #5:

score: 19
Accepted
time: 121ms
memory: 19228kb

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
3
4
5
7
4
1
4
3
7
14
2
7
3
18
17
11
4
13
2
2
18
21
12
17
3
3
22
22
6
5
20
5
17
22
27
18
23
31
4
1
19
21
12
22
34
33
5
22
40
40
8
14
42
35
9
40
24
18
13
36
8
25
49
32
34
47
14
47
19
38
10
14
31
40
17
20
45
46
1
35
1
43
9
47
33
56
2
8
19
41
21
18
50
22
61
27
2
2
6
4
58
62
35
61
59
10...

result:

ok 179182 lines

Test #6:

score: 19
Accepted
time: 123ms
memory: 23336kb

input:

1 296745
1 0
3 1
3 1
1 0
1 0
3 2
1 0
3 4
1 4
1 0
1 4
3 5
1 0
1 0
1 0
1 0
1 8
1 4
1 0
1 0
1 8
3 9
1 0
1 8
1 4
1 0
1 0
1 0
1 0
3 3
1 0
1 7
1 0
1 0
1 7
1 9
1 3
3 15
1 0
1 3
1 10
3 16
1 0
1 0
1 0
3 10
1 10
1 0
1 0
3 11
1 0
1 0
3 29
1 0
3 26
3 16
1 0
1 0
1 0
1 0
1 0
1 1
1 0
1 5
1 1
3 21
3 36
3 42
3 23
3 ...

output:

1
1
2
1
4
5
21
9
19
16
17
24
11
28
21
12
7
19
19
55
37
55
24
47
1
62
37
44
39
59
30
85
48
5
8
46
61
74
39
34
67
12
58
1
107
83
87
60
12
93
119
81
37
51
112
25
125
55
98
94
9
71
46
33
121
64
4
128
144
128
100
10
133
25
170
107
179
19
19
9
2
144
192
110
28
172
115
101
162
108
48
83
6
169
171
18
194
40...

result:

ok 98880 lines

Test #7:

score: 19
Accepted
time: 130ms
memory: 21500kb

input:

1 297653
1 0
3 1
1 1
3 2
1 2
3 1
1 0
1 1
3 1
3 3
1 2
3 4
1 2
3 2
3 1
1 0
3 6
3 8
1 5
3 6
1 6
3 4
1 2
1 5
3 9
3 3
1 9
3 4
1 6
3 6
3 5
1 4
1 8
3 2
3 5
1 1
3 17
3 12
1 7
1 10
1 0
1 8
1 10
3 21
3 12
3 2
1 5
1 8
3 12
3 8
1 4
3 24
3 2
3 1
3 3
1 6
1 8
1 8
3 4
1 0
3 5
3 27
1 2
3 22
1 8
1 10
1 1
1 8
1 5
1 3
...

output:

1
2
1
2
5
1
4
2
7
1
8
2
6
12
2
11
4
10
6
6
8
3
10
13
12
2
3
16
9
25
8
14
5
28
8
16
30
11
1
11
28
22
41
7
5
32
52
7
25
24
48
46
31
41
43
52
41
27
22
48
63
39
2
56
69
11
78
8
47
35
70
43
47
50
30
86
85
17
42
7
91
51
44
30
47
29
59
90
43
92
85
98
55
23
43
106
76
39
26
109
110
40
10
110
73
108
67
42
107...

result:

ok 148504 lines

Test #8:

score: 19
Accepted
time: 94ms
memory: 17268kb

input:

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

output:

1
2
1
5
5
1
3
1
7
7
2
2
5
1
12
7
3
3
12
7
1
8
6
15
18
14
12
15
18
4
12
18
1
11
9
10
9
18
6
4
8
3
4
8
29
3
14
34
4
18
22
22
32
17
36
1
24
8
11
17
24
8
38
26
17
16
36
14
49
38
7
19
29
19
19
4
29
36
21
46
2
5
50
12
54
47
22
15
13
63
13
63
19
39
56
72
66
35
44
57
11
21
52
11
73
43
23
16
17
24
58
47
26
4...

result:

ok 167157 lines

Test #9:

score: 19
Accepted
time: 123ms
memory: 21516kb

input:

1 291033
1 0
1 1
3 1
3 1
1 2
1 0
3 4
3 3
3 1
3 3
3 2
1 1
1 5
3 5
3 2
1 1
1 5
1 5
3 7
3 1
3 8
3 3
3 8
1 2
3 5
1 6
3 11
3 1
1 9
3 8
3 6
1 4
3 1
3 8
1 10
3 1
1 2
1 5
3 7
3 15
1 1
3 7
3 12
1 6
1 5
1 0
1 3
3 20
3 1
3 12
1 9
3 18
3 17
1 5
3 5
1 5
1 7
3 19
1 1
3 3
3 3
1 1
3 26
1 4
1 7
1 7
1 5
3 26
3 18
1 0...

output:

1
1
1
4
2
4
3
3
5
3
2
6
9
6
4
8
2
7
8
3
8
3
4
13
5
9
1
4
11
15
5
7
11
25
25
6
7
24
36
3
31
31
43
3
49
20
39
29
9
47
12
55
3
38
34
14
57
7
15
50
60
24
55
8
25
34
34
7
21
62
72
69
19
14
26
70
20
37
35
14
77
71
80
13
56
2
9
20
28
63
82
14
75
69
26
101
84
70
75
30
37
49
42
65
54
41
110
107
86
69
2
34
10...

result:

ok 145645 lines

Test #10:

score: 19
Accepted
time: 103ms
memory: 21544kb

input:

1 296808
1 0
3 1
1 0
1 0
1 0
3 3
1 3
1 0
3 3
1 0
3 5
3 5
3 2
3 1
3 3
1 0
1 0
1 6
1 9
3 6
1 0
1 6
3 12
1 0
1 2
1 0
3 13
3 1
1 0
3 13
1 8
1 2
3 18
1 0
1 10
1 0
1 0
3 22
3 21
3 10
1 0
1 0
1 3
3 8
3 26
3 5
1 0
3 11
1 0
3 4
3 9
3 19
1 0
3 15
3 29
1 10
1 0
3 18
3 8
1 0
1 4
1 0
3 34
1 0
1 0
1 4
3 20
1 3
1 ...

output:

1
2
3
5
5
6
7
4
5
1
9
16
10
8
2
16
15
12
21
22
12
21
12
26
28
1
17
16
1
13
16
33
14
26
26
34
4
41
44
46
33
9
37
24
22
39
37
48
20
25
17
31
55
69
52
16
5
54
40
46
49
12
23
69
15
29
37
81
4
26
9
5
61
89
75
24
4
17
5
25
63
75
57
96
21
75
105
35
83
93
55
59
31
35
54
109
103
83
68
59
2
47
122
5
95
57
116...

result:

ok 148730 lines

Test #11:

score: 19
Accepted
time: 80ms
memory: 18804kb

input:

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

output:

4
2
5
1
1
3
2
5
1
7
4
2
1
4
9
11
4
4
1
1
6
10
10
11
7
11
6
11
17
6
5
1
16
11
2
6
3
10
4
4
6
8
9
3
6
2
7
18
6
13
5
19
2
5
15
1
23
18
7
5
7
2
5
1
26
14
15
19
4
24
15
1
5
15
6
14
21
22
2
26
24
27
1
8
16
29
29
22
8
8
18
7
19
30
9
27
9
22
16
26
33
11
16
1
28
21
29
19
31
21
11
30
36
20
23
25
28
28
27
32
3...

result:

ok 234925 lines

Test #12:

score: 19
Accepted
time: 146ms
memory: 20800kb

input:

1 296974
1 0
1 0
1 1
1 1
1 4
3 2
1 1
3 6
1 6
1 3
3 5
3 8
3 8
1 5
3 9
1 7
3 1
3 3
1 8
3 9
1 11
1 12
1 12
1 6
1 6
1 10
1 13
3 15
1 14
1 17
1 20
3 21
3 1
1 13
1 18
3 9
3 18
3 16
1 22
3 22
3 4
1 24
1 20
1 18
3 26
1 25
3 12
3 3
3 19
3 28
1 26
3 13
3 14
1 26
1 29
3 26
3 13
1 26
1 32
3 32
1 25
1 25
3 27
1 ...

output:

1
3
6
8
8
7
2
9
8
5
10
2
13
22
4
21
11
10
18
15
20
25
22
20
10
24
11
34
19
29
21
13
26
15
20
48
28
48
5
18
49
24
16
22
16
75
53
71
13
27
11
41
73
36
47
52
62
84
18
61
83
82
4
49
84
8
81
67
91
26
44
41
2
61
77
89
74
79
30
69
63
60
96
61
79
11
79
79
100
68
4
42
11
51
44
85
12
92
81
99
12
40
106
36
31
...

result:

ok 126807 lines

Test #13:

score: 19
Accepted
time: 92ms
memory: 19284kb

input:

1 293712
1 0
3 1
1 1
1 0
3 1
1 0
1 0
1 0
1 0
1 0
3 5
3 3
3 2
1 7
1 0
1 7
3 4
1 6
3 7
3 10
3 5
1 4
1 0
3 3
3 7
3 6
1 9
3 12
3 12
3 12
3 15
3 6
1 0
1 0
1 0
1 4
3 6
3 6
1 0
1 3
1 0
3 16
3 5
1 6
3 9
3 22
3 4
1 0
3 17
1 2
1 7
1 0
1 0
3 12
3 28
1 2
1 4
3 15
1 4
3 5
3 13
3 27
3 3
3 6
1 0
3 27
3 21
1 5
3 8
...

output:

1
2
4
6
8
8
3
1
8
12
4
7
9
9
9
7
8
11
11
5
15
11
1
17
5
19
1
16
20
25
2
26
17
3
28
12
11
9
13
28
3
2
6
9
16
11
23
32
28
9
2
21
4
46
17
32
18
4
42
55
41
37
21
19
43
38
10
3
25
16
38
16
50
62
24
70
32
63
83
79
42
7
81
26
72
58
16
85
93
14
33
44
87
64
15
52
84
63
34
16
82
121
59
85
65
22
74
44
81
10
23...

result:

ok 126007 lines

Test #14:

score: 19
Accepted
time: 109ms
memory: 19852kb

input:

1 292001
1 0
3 1
3 1
1 0
3 2
3 2
1 2
1 1
3 1
1 4
3 4
1 0
3 2
1 1
3 2
1 4
3 5
1 5
3 6
1 3
1 9
1 0
1 3
3 1
3 2
1 0
1 0
1 2
3 13
3 1
1 0
3 15
1 0
1 3
3 6
1 0
3 9
1 4
1 0
3 10
1 0
1 7
1 0
3 3
1 6
1 0
1 0
1 0
1 4
1 0
1 0
3 2
1 1
1 2
3 17
1 4
3 13
1 5
1 0
1 0
1 0
3 22
1 0
3 35
1 6
1 0
3 15
1 0
1 0
3 23
3 ...

output:

1
1
1
1
3
4
2
2
8
1
7
3
8
10
2
6
19
14
13
17
11
22
11
33
17
14
42
8
24
47
40
62
21
34
29
71
41
6
42
38
3
62
5
41
45
12
16
54
22
43
84
84
53
14
69
34
57
18
82
32
86
17
73
50
38
43
32
79
11
57
44
65
44
108
53
22
103
90
60
41
108
122
17
73
144
136
176
108
18
30
66
191
181
87
14
195
135
67
107
154
23
12...

result:

ok 97400 lines

Test #15:

score: 19
Accepted
time: 148ms
memory: 21088kb

input:

1 295477
1 0
3 1
1 0
3 1
1 2
1 3
1 1
3 2
1 3
1 5
3 4
3 2
3 2
1 1
1 1
1 2
1 4
1 10
3 9
3 11
1 7
3 13
1 13
1 12
1 6
1 16
1 8
1 11
1 10
3 14
3 9
3 7
1 12
1 16
1 19
1 17
1 24
3 8
3 12
1 21
3 25
1 21
1 25
1 24
3 9
1 28
3 21
3 12
1 25
1 26
3 21
1 25
3 22
3 16
1 28
3 30
3 11
3 13
1 34
3 23
1 29
3 24
3 27
1...

output:

1
2
1
4
1
1
9
7
13
20
14
18
20
4
14
23
5
4
5
13
12
22
24
33
27
15
6
36
39
22
6
7
13
16
28
43
2
21
7
41
33
24
20
30
49
26
57
50
43
48
59
15
33
67
53
56
42
50
23
13
69
46
64
58
67
24
44
70
32
64
15
51
21
7
89
87
40
78
95
90
34
64
17
102
24
122
45
94
15
107
133
36
131
107
65
5
57
12
69
115
153
152
40
5...

result:

ok 117628 lines

Test #16:

score: 19
Accepted
time: 101ms
memory: 16804kb

input:

1 291841
1 0
1 1
3 2
1 0
3 3
1 3
3 1
3 3
3 3
1 2
3 4
3 1
3 4
1 1
3 3
3 3
3 5
1 3
1 3
3 2
1 6
3 6
3 2
1 8
1 9
1 4
3 4
3 1
3 12
1 6
3 11
3 3
3 9
3 2
3 7
3 10
1 7
3 3
1 9
3 13
3 4
3 6
1 6
1 1
3 11
3 8
1 1
1 1
3 9
1 4
3 9
3 2
3 20
1 8
1 8
3 11
1 8
3 6
1 6
3 19
1 5
1 9
1 9
3 10
3 16
1 6
3 2
1 9
3 11
3 11...

output:

2
1
3
1
1
2
3
2
1
1
6
7
6
8
5
7
6
11
1
10
12
4
3
1
10
6
9
15
2
15
16
19
7
20
16
13
6
18
26
26
26
15
21
16
19
30
13
4
8
7
35
5
5
3
2
18
22
8
26
9
33
38
7
19
21
4
22
33
39
24
28
25
14
9
32
9
24
17
16
24
31
36
32
38
1
9
11
41
20
13
12
49
45
8
5
3
32
30
40
22
34
48
7
29
33
48
23
49
19
27
40
24
55
36
4
5...

result:

ok 194540 lines

Test #17:

score: 19
Accepted
time: 143ms
memory: 22128kb

input:

1 298768
1 0
1 0
1 2
1 2
1 0
1 0
1 1
1 6
1 0
1 7
1 9
1 10
1 6
3 11
1 4
3 8
1 10
1 6
3 15
1 5
1 8
3 18
1 0
1 10
1 9
1 0
1 3
1 3
1 0
1 9
1 1
1 10
1 6
1 1
3 16
1 8
1 0
3 15
1 9
1 2
1 3
1 3
1 10
3 18
1 8
3 8
1 10
1 7
1 6
3 22
1 5
3 35
1 1
3 38
1 8
1 10
3 6
1 6
1 3
1 0
3 36
1 8
1 3
1 2
3 29
1 4
1 4
1 3
1...

output:

2
5
15
7
10
31
16
14
3
28
16
10
31
14
24
51
58
76
43
3
14
67
7
27
18
33
75
6
89
12
21
88
14
34
1
84
10
18
49
24
60
87
80
116
16
148
72
99
101
157
102
1
159
101
57
149
159
164
112
74
89
43
194
131
135
10
31
85
91
187
84
66
136
61
217
58
114
76
116
182
31
114
124
228
91
124
20
109
154
258
203
136
162
...

result:

ok 74993 lines

Test #18:

score: 19
Accepted
time: 120ms
memory: 21944kb

input:

1 297636
1 0
3 1
1 0
3 2
3 2
1 0
3 2
1 0
1 0
3 5
3 3
1 5
1 0
3 2
1 0
1 6
1 9
1 0
1 8
1 0
3 2
3 3
3 2
1 3
3 14
3 13
1 0
1 0
3 16
1 0
3 12
1 5
1 0
1 0
1 8
1 0
1 8
1 0
1 5
1 2
3 14
1 0
1 0
1 0
1 0
1 0
3 14
1 0
1 9
1 0
3 26
1 0
3 25
3 1
3 15
1 0
1 0
3 34
3 1
1 9
1 0
1 0
3 17
1 2
1 8
1 0
3 31
1 10
1 0
1 ...

output:

1
1
1
2
1
3
6
12
11
12
12
1
1
7
23
28
33
24
35
15
4
37
17
9
7
25
29
12
37
47
13
38
45
5
6
50
51
49
57
47
19
16
46
60
55
51
49
18
59
6
70
17
59
12
65
61
86
57
51
92
43
12
11
46
64
39
47
85
27
111
79
14
41
12
1
47
28
23
13
130
87
92
67
73
16
68
66
51
118
158
145
78
99
34
42
157
161
97
166
169
171
106
...

result:

ok 98914 lines

Test #19:

score: 19
Accepted
time: 101ms
memory: 17124kb

input:

1 291909
1 0
1 0
1 1
1 2
3 1
3 2
3 3
1 3
3 5
1 1
3 1
3 1
3 5
3 4
1 0
3 4
3 5
3 7
3 3
3 7
3 6
1 5
1 3
1 9
3 6
3 1
3 8
1 2
3 8
3 6
3 10
3 8
3 4
1 2
1 1
3 2
3 11
1 2
3 13
1 3
1 8
1 4
3 1
3 7
3 12
3 15
1 0
3 14
3 13
3 6
3 1
3 17
3 14
3 2
1 5
3 16
3 1
3 10
3 2
1 1
3 13
1 10
3 16
1 4
1 2
1 4
3 8
3 10
3 24...

output:

3
1
4
5
3
3
6
2
3
7
1
6
1
5
5
4
10
11
6
9
11
4
2
4
8
8
1
4
12
4
10
11
9
8
4
3
19
9
15
3
11
21
23
19
9
5
21
13
25
13
15
30
30
12
17
17
11
28
30
12
15
32
20
8
6
20
6
29
18
36
21
15
13
21
2
40
18
5
42
5
15
29
50
7
8
23
49
30
27
14
26
60
52
4
15
25
56
10
44
21
61
45
25
4
34
59
64
65
64
33
50
64
47
34
63...

result:

ok 166650 lines

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 93ms
memory: 16928kb

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
10
5
10
8
5
8
9
8
11
1
2
1
8
6
11
9
3
2
4
4
9
3
15
13
12
4
9
4
12
10
6
2
4
10
9
16
2
15
13
13
7
3
3
11
21
7
5
4
2
10
5
15
20
6
17
12
5
24
4
15
13
7
10
17
6
19
9
19
19
12
3
18
16
21
19
26
12
25
21
19
10
14
24
8
8
14
16
32
8
14
33
30
14
4
1
20
21
37
22
25
7
18
27
28
35
37
18
33
4...

result:

wrong answer 24425th lines differ - expected: '5380', found: '5379'

Subtask #4:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 512ms
memory: 17068kb

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
4
3
2
3
4
4
1
2
3
3
3
2
2
4
5
8
9
9
6
5
6
6
2
6
17
19
20
12
23
5
20
5
5
8
3
27
27
20
25
23
3
35
31
35
7
13
34
8
42
8
20
45
4
23
22
20
26
17
52
19
39
18
28
39
57
47
19
11
55
8
52
52
24
6
2
14
19
38
40
27
50
52
13
51
10
67
33
35
57
66
58
51
84
75
76
14
20
38
67
62
106
25
42
67
49
114
67
82
38
103
...

result:

wrong answer 21st lines differ - expected: '7', found: '6'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2025-02-01 16:48:46 | OpenSource Project