QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#818373#8704. 排队Sktn008919 369ms71544kbC++143.3kb2024-12-17 19:32:072024-12-17 19:32:13

Judging History

This is the latest submission verdict.

  • [2024-12-17 19:32:13]
  • Judged
  • Verdict: 19
  • Time: 369ms
  • Memory: 71544kb
Show
  • [2024-12-17 19:32:07]
  • Submitted

answer

#include <bits/stdc++.h>

namespace Initial {
	#define ll int
	#define ull unsigned long long
	#define fi first
	#define se second
	#define mkp make_pair
	#define pir pair <int, int>
	#define pb push_back
	#define i128 __int128
	using namespace std;
	const ll maxn = 6e5 + 10, inf = 1e9, mod = 1e9 + 7;
	ll power(ll a, ll b = mod - 2) {
		ll s = 1;
		while(b) {
			if(b & 1) s = 1ll * s * a %mod;
			a = 1ll * a * a %mod, b >>= 1;
		} return s;
	}
	template <class T>
	const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
	template <class T>
	const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
	template <class T>
	const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
	template <class T>
	const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;

namespace Read {
	char buf[1 << 22], *p1, *p2;
//	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
	template <class T>
	const inline void rd(T &x) {
		char ch; bool neg = 0;
		while(!isdigit(ch = getchar()))
			if(ch == '-') neg = 1;
		x = ch - '0';
		while(isdigit(ch = getchar()))
			x = (x << 1) + (x << 3) + ch - '0';
		if(neg) x = -x;
	}
} using Read::rd;

ll n, m; set <ll> st[maxn];
mt19937 rnd(20090623);

struct Treap {
	ll fa[maxn], siz[maxn], lc[maxn], rc[maxn], dnr[maxn];
	ll val[maxn], cnt[maxn];
	void pushup(ll p) {
		siz[p] = siz[lc[p]] + siz[rc[p]] + 1;
		cnt[p] = cnt[lc[p]] + cnt[rc[p]] + val[p];
	}
	ll merge(ll p, ll q) {
		fa[p] = fa[q] = 0;
		if(!p || !q) return p | q;
		if(dnr[p] < dnr[q])
			return pushup(fa[rc[p] = merge(rc[p], q)] = p), p;
		else
			return pushup(fa[lc[q] = merge(p, lc[q])] = q), q;
	}
	void split(ll p, ll k, ll &x, ll &y) {
		if(!p) return x = y = 0, void();
		fa[p] = 0;
		if(siz[lc[p]] + 1 <= k) {
			split(rc[p], k - 1 - siz[lc[p]], rc[p], y);
			return fa[rc[p]] = p, pushup(x = p);
		} else {
			split(lc[p], k, x, lc[p]);
			return fa[lc[p]] = p, pushup(y = p);
		}
	}
	ll getrk(ll p) {
		ll s = siz[lc[p]] + 1;
		for(ll q = p; p = fa[p]; q = p)
			if(rc[p] == q) s += siz[lc[p]] + 1;
		return s;
	}
	ll qry(ll p) {
		ll s = cnt[lc[p]] + val[p];
		for(ll q = p; p = fa[p]; q = p)
			if(rc[p] == q) s += cnt[lc[p]] + val[p];
		return s;
	}
	void Newnode(ll p, ll w) {
		siz[p] = 1, dnr[p] = rnd(), cnt[p] = val[p] = w;
	} 
} tr; ll rt, f[maxn];

signed main() {
	rd(n), rd(n); st[0].insert(inf);
	while(n--) {
		ll op, x; rd(op), rd(x);
		if(op == 1) {
			st[x].insert(++m), f[m] = x, st[m].insert(inf);
			tr.Newnode(2 * m, 0), tr.Newnode(2 * m - 1, 1);
			ll k = x? tr.getrk(2 * x - 1) : 0;
			ll s1, s2; tr.split(rt, k, s1, s2);
			rt = tr.merge(tr.merge(s1, tr.merge(2 * m - 1, 2 * m)), s2);
		} else if(op == 2) {
			ll y; rd(y);
			ll k1 = tr.getrk(2 * x - 1), k2 = tr.getrk(2 * x);
			ll s1, sx, s2; tr.split(rt, k2, s1, s2);
			tr.split(s1, k1 - 1, s1, sx);
			rt = tr.merge(s1, s2);
			ll z = *st[y].upper_bound(x);
			ll k = y? tr.getrk(z == inf? 2 * y - 1 : 2 * z) : 0;
			tr.split(rt, k, s1, s2);
			rt = tr.merge(tr.merge(s1, sx), s2);
			st[f[x]].erase(x), st[f[x] = y].insert(x);
		} else {
			printf("%d\n", tr.qry(2 * x - 1));
		}
	}
	return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 3ms
memory: 42724kb

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: 42772kb

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
1
1
9
9
11
7
5
2
3
5
9
19
12
10
20
17
15
9
25
1
24
18
19
11
17
26
2
7
31
28
23
24
37
22
35
8
53
11
20
55
16
20
46
4
8
56
40
43
48
18
49
18
20
15
49
62
9
58
7
50
57
49
74
73
52
12
28
42
42
21
25
21
24
79
68
46
5
23
81
88
14
51
74
11
65
98
19
52
62
102
33
59
39
88
63
67
38
103
94
36
77
14
...

result:

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

Subtask #2:

score: 19
Accepted

Test #5:

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

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: 148ms
memory: 67312kb

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: 141ms
memory: 61860kb

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: 105ms
memory: 59092kb

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: 143ms
memory: 61964kb

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: 130ms
memory: 61912kb

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: 94ms
memory: 49968kb

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: 138ms
memory: 63632kb

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: 121ms
memory: 63352kb

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: 130ms
memory: 66596kb

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: 131ms
memory: 65432kb

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: 116ms
memory: 56364kb

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: 178ms
memory: 69648kb

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: 138ms
memory: 67148kb

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: 139ms
memory: 58196kb

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: 21
Accepted
time: 93ms
memory: 51768kb

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:

ok 222965 lines

Test #21:

score: 21
Accepted
time: 116ms
memory: 56552kb

input:

2 297805
1 0
1 0
3 1
3 1
1 0
1 1
3 2
1 0
3 4
3 3
3 3
3 3
3 4
3 3
1 0
3 4
1 2
3 2
3 7
1 5
1 0
1 0
1 10
3 5
3 6
1 0
1 0
1 0
3 9
1 0
3 3
1 0
1 0
3 13
3 15
3 2
3 15
3 6
3 2
3 17
1 5
3 14
3 9
1 1
3 5
3 10
3 13
3 17
3 7
1 0
3 20
3 6
3 14
1 0
1 4
3 10
3 19
1 0
3 6
3 5
3 13
3 4
3 19
1 7
3 14
3 6
3 15
3 20
3...

output:

2
2
2
5
2
2
2
5
2
6
4
5
5
4
6
11
5
3
14
3
10
14
1
4
9
11
7
5
1
16
1
11
5
9
20
13
14
8
22
21
7
13
6
3
3
15
22
2
11
7
10
17
13
10
13
20
17
5
33
10
12
28
9
26
27
12
36
18
2
22
2
24
35
34
4
4
12
34
35
8
18
14
1
38
33
10
35
10
7
5
27
54
47
7
42
16
12
15
46
45
18
24
29
28
51
50
40
42
16
46
22
9
28
46
4
1
...

result:

ok 197988 lines

Test #22:

score: 21
Accepted
time: 181ms
memory: 71544kb

input:

2 292846
1 0
3 1
3 1
1 1
1 1
1 3
1 0
1 0
1 5
1 7
3 2
3 4
1 8
1 1
1 6
1 8
1 7
1 1
1 10
1 9
3 6
1 5
1 6
3 7
1 3
1 3
1 5
1 6
1 4
1 6
1 1
1 6
1 9
1 5
3 23
1 7
1 8
1 3
1 1
1 4
3 8
1 6
1 1
1 8
1 2
1 5
1 3
1 5
1 9
3 25
1 10
1 6
1 9
3 44
1 7
3 26
1 1
1 7
1 5
1 9
3 34
1 9
1 3
1 6
1 0
1 6
1 0
1 9
3 53
1 10
1 ...

output:

1
1
8
7
1
6
27
14
28
23
4
3
2
57
9
34
43
87
64
13
1
63
88
2
83
38
89
101
97
82
57
115
145
57
34
57
15
147
126
107
108
140
37
91
177
16
135
205
227
171
152
88
31
95
21
231
40
20
273
201
128
82
98
147
115
169
238
129
58
179
114
268
324
39
163
132
251
230
65
16
295
299
15
272
28
312
255
358
315
229
193...

result:

ok 58684 lines

Test #23:

score: 21
Accepted
time: 125ms
memory: 65124kb

input:

2 294522
1 0
1 0
3 2
1 2
1 1
3 1
3 2
1 4
3 2
1 0
1 5
3 6
3 7
1 1
3 8
1 2
1 3
1 10
3 4
3 3
3 1
1 4
1 4
3 6
1 9
1 13
3 8
1 9
1 13
1 9
3 3
3 16
3 2
3 3
3 18
3 16
1 10
3 9
1 14
3 19
1 12
3 6
3 10
1 13
3 2
1 21
1 15
1 21
3 5
1 24
1 25
1 23
1 26
1 23
3 27
1 30
1 24
1 26
1 29
1 30
1 34
1 28
1 34
3 25
1 33
...

output:

1
3
1
1
1
7
5
9
4
7
1
9
7
5
2
7
4
5
3
10
1
9
2
24
25
29
4
15
17
8
12
23
32
28
44
43
4
14
29
28
63
59
57
63
12
60
57
63
50
12
11
54
19
2
41
71
55
72
70
66
29
65
89
21
56
3
75
56
62
65
67
22
6
108
109
62
7
56
51
43
80
118
101
87
18
83
109
19
77
91
88
19
24
31
83
87
146
13
106
52
133
44
93
56
84
51
139...

result:

ok 117694 lines

Test #24:

score: 21
Accepted
time: 131ms
memory: 60920kb

input:

2 295234
1 0
1 1
3 1
3 2
3 1
1 0
3 2
3 3
3 3
3 3
3 2
1 0
1 2
3 1
1 5
1 0
1 1
1 4
1 7
1 1
1 1
3 1
1 10
1 0
3 8
1 0
1 0
3 12
1 8
3 9
1 0
3 3
3 9
3 7
3 12
3 15
1 0
1 0
1 0
3 16
3 7
1 1
1 0
3 9
3 15
3 18
1 0
1 7
1 0
3 22
3 21
3 24
3 14
3 25
1 9
1 0
1 0
1 6
3 2
1 3
1 0
1 0
1 7
1 0
1 0
1 0
1 0
1 0
1 0
1 0...

output:

1
2
1
3
1
1
1
3
3
6
11
11
8
10
9
5
12
3
5
8
13
7
5
19
4
2
10
12
27
34
19
39
29
3
31
12
13
29
10
33
18
51
46
55
6
7
22
38
49
17
9
30
30
43
17
40
44
23
52
21
18
61
56
71
14
4
55
46
50
20
51
19
31
16
50
3
13
58
7
85
21
41
14
90
22
74
65
64
10
2
62
75
21
49
82
4
71
11
6
99
44
50
58
45
1
58
46
80
65
68
4...

result:

ok 147378 lines

Test #25:

score: 21
Accepted
time: 110ms
memory: 60596kb

input:

2 290392
1 0
3 1
3 1
1 1
3 1
1 0
3 2
1 0
3 2
3 4
1 3
3 4
1 4
3 2
3 1
1 2
1 4
1 4
3 3
3 8
1 1
3 1
3 10
1 1
3 7
1 4
3 12
3 1
1 10
3 10
3 12
1 13
3 6
1 8
1 11
3 8
3 10
3 1
3 2
3 13
1 14
3 3
1 8
3 8
1 18
3 10
3 3
1 14
1 12
1 18
1 15
3 11
3 1
3 19
1 14
1 17
3 5
1 23
3 14
1 24
1 26
1 20
3 8
3 8
3 13
1 22
...

output:

1
1
1
3
4
1
1
6
5
5
3
7
8
11
2
8
10
2
5
4
12
9
15
13
7
4
14
9
15
14
8
13
20
5
5
20
13
20
29
20
23
18
2
15
3
19
5
8
10
29
47
22
49
45
34
20
32
2
40
30
41
15
6
36
11
48
7
35
73
37
8
30
37
63
82
30
35
60
4
27
15
44
18
34
1
21
78
39
54
58
23
53
46
31
11
32
70
100
22
94
105
58
117
13
35
22
51
114
87
70
9...

result:

ok 144784 lines

Test #26:

score: 0
Wrong Answer
time: 126ms
memory: 64032kb

input:

2 290273
1 0
1 0
3 1
1 0
1 0
3 4
1 0
3 4
3 3
3 1
1 0
3 3
1 0
3 5
3 4
3 1
3 2
1 0
3 6
1 0
1 7
3 6
1 2
1 1
1 5
3 4
1 3
3 9
1 10
3 4
3 9
1 4
1 0
1 0
3 6
3 1
1 0
1 6
3 16
1 10
1 9
1 0
1 0
1 0
1 2
3 21
1 6
1 0
1 0
3 24
1 1
1 0
1 0
3 26
3 18
1 9
1 6
1 0
3 35
1 4
3 36
1 0
1 5
1 8
1 5
1 2
3 36
1 0
1 6
1 0
1...

output:

2
1
2
3
5
4
3
4
7
6
3
5
8
1
9
1
8
17
14
12
4
28
9
1
27
31
42
23
25
37
14
13
4
16
2
7
37
36
39
43
10
33
30
11
9
53
42
26
7
56
77
63
55
11
44
78
23
69
14
87
54
28
52
17
49
15
26
92
47
93
92
105
16
116
94
1
40
85
77
82
60
94
120
97
31
85
56
10
32
61
133
136
80
60
73
60
115
104
21
30
18
164
96
8
149
83
...

result:

wrong answer 16989th lines differ - expected: '6395', found: '6396'

Subtask #4:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 369ms
memory: 56880kb

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
2
1
1
3
4
7
8
8
5
4
10
6
14
9
20
14
15
7
18
4
4
9
9
23
7
10
11
28
14
16
9
16
38
16
30
27
3
36
14
38
8
2
16
10
27
29
50
48
12
30
17
30
3
2
55
33
28
43
16
44
61
22
7
5
31
29
9
18
60
13
64
27
17
65
14
83
54
67
62
34
32
83
22
1
1
41
65
8
25
36
106
14
38
24
28
60
24
19
52
63
121
8...

result:

wrong answer 13th lines differ - expected: '3', found: '2'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2025-02-08 15:07:37 | 开源项目