QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203140#2484. ScreamersPlentyOfPenalty#AC ✓71ms10636kbC++202.5kb2023-10-06 15:42:352023-10-06 15:42:35

Judging History

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

  • [2023-10-06 15:42:35]
  • 评测
  • 测评结果：AC
  • 用时：71ms
  • 内存：10636kb
查看
  • [2023-10-06 15:42:35]
  • 提交

answer

#include "bits/stdc++.h"
typedef long long ll;
const int MAXN = 200011;
struct LCT
{
	int fa[MAXN],son[MAXN][2];
	bool rev[MAXN];
	bool not_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
	void reverse(int x)
	{
		if(!x)return;
		std::swap(son[x][0],son[x][1]);
		rev[x]^=1;
	}
	void pushdown(int x)
	{
		if(rev[x])
		{
			reverse(son[x][0]),reverse(son[x][1]);
			rev[x]=0;
		}
	}
	void rotate(int x)
	{
		int y=fa[x],z=fa[y],k=(son[y][1]==x);
		if(not_root(y))son[z][son[z][1]==y]=x;
		fa[x]=z,fa[y]=x;
		fa[son[x][!k]]=y,son[y][k]=son[x][!k];
		son[x][!k]=y;
	}
	int s[MAXN];
	void splay(int x)
	{
		int top=0,y=x;
		s[++top]=y;
		while(not_root(y))s[++top]=y=fa[y];
		while(top)pushdown(s[top--]);
		while(not_root(x))
		{
			int y=fa[x];
			if(not_root(y))
				rotate((son[y][1]==x)==(son[fa[y]][1]==y)?y:x);
			rotate(x);
		}
	}
	void access(int x)
	{
		for(int y=0;x;y=x,x=fa[x])
			splay(x),son[x][1]=y;
	}
	int get_root(int x)
	{
		access(x),splay(x),pushdown(x);
		while(son[x][0])pushdown(x=son[x][0]);
		splay(x);
		return x;
	}
	bool check(int x,int y)
	{
		// printf("check(%d,%d)\n",x,y);
		return get_root(x)==get_root(y);
	}
	void make_root(int x)
	{
		access(x),splay(x);
		reverse(x);
	}
	void link(int x,int y)
	{
		// printf("link (%d,%d)\n",x,y);
		make_root(x);
		fa[x]=y;
	}
	void cut(int x,int y)
	{
		// printf("cut(%d,%d)\n",x,y);
		make_root(x),get_root(y);
		// printf("y=%d,fa=%d,ls=%d,rs=%d\n",y,fa[y],son[y][0],son[y][1]);
		pushdown(x);
		if(son[x][1]==y&&!son[y][0]&&!son[y][1])
		{
			son[x][1]=0,fa[y]=0;
		}
		else fprintf(stderr,"Error: Cut (%d,%d) failed!\n",x,y);
	}
}t;
typedef std::pair<int,int> pii;
pii ed[MAXN];
int f[MAXN];
ll sum[MAXN];
int main()
{
	//freopen("K.in","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d%d",&ed[i].first,&ed[i].second);
	int l=1,r=1;
	while(l<=m)
	{
		while(r<=m&&!t.check(ed[r].first,ed[r].second))
		{
			t.link(ed[r].first,ed[r].second);
			++r;
		}
		f[l]=r-1;
		// printf("F[%d]=%d\n",l,r-1);
		t.cut(ed[l].first,ed[l].second);
		++l;
	}
	for(int i=1;i<=m;++i)sum[i]=sum[i-1]+f[i];
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int p=std::lower_bound(f+1,f+m+1,r)-f;
		ll dec=ll(r-l+1)*(l-1+r-1)/2;
		if(p<=l)printf("%lld\n",ll(r-l+1)*r-dec);
		else
		{
			ll ans=sum[p-1]-sum[l-1];
			ans+=ll(r-p+1)*r;
			printf("%lld\n",ans-dec);
		}
	}
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5684kb

input:

4 6
1 2
2 3
1 3
1 4
3 4
2 4
4
1 1
1 3
2 4
1 6

output:

1
5
6
13

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

3 3
1 2
1 3
2 3
6
1 1
1 2
1 3
2 2
2 3
3 3

output:

1
3
5
1
3
1

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 7660kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4
21
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 3
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6

output:

1
3
6
9
12
14
1
3
6
9
11
1
3
6
8
1
3
5
1
3
1

result:

ok 21 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 7664kb

input:

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
55
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 5
5 6
5 7
5 8
5 9
5 10
6 6
6 7
6 8
6 9
6 10
7 7
7 8
7 9
7 10
8 8
8 9
8 10
9 9
9 10
10 10

output:

1
3
6
10
14
18
22
25
28
30
1
3
6
10
14
18
21
24
26
1
3
6
10
14
17
20
22
1
3
6
10
13
16
18
1
3
6
9
12
14
1
3
6
9
11
1
3
6
8
1
3
5
1
3
1

result:

ok 55 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 7964kb

input:

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

output:

1
3
6
10
15
20
25
30
35
39
43
47
50
53
55
1
3
6
10
15
20
25
30
34
38
42
45
48
50
1
3
6
10
15
20
25
29
33
37
40
43
45
1
3
6
10
15
20
24
28
32
35
38
40
1
3
6
10
15
19
23
27
30
33
35
1
3
6
10
14
18
22
25
28
30
1
3
6
10
14
18
21
24
26
1
3
6
10
14
17
20
22
1
3
6
10
13
16
18
1
3
6
9
12
14
1
3
6
9
11
1
3
6...

result:

ok 120 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 7808kb

input:

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

output:

1
3
6
10
15
21
27
33
39
45
51
56
61
66
71
75
79
83
86
89
91
1
3
6
10
15
21
27
33
39
45
50
55
60
65
69
73
77
80
83
85
1
3
6
10
15
21
27
33
39
44
49
54
59
63
67
71
74
77
79
1
3
6
10
15
21
27
33
38
43
48
53
57
61
65
68
71
73
1
3
6
10
15
21
27
32
37
42
47
51
55
59
62
65
67
1
3
6
10
15
21
26
31
36
41
45
...

result:

ok 231 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

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

output:

1
3
6
10
15
21
28
35
42
49
56
63
70
76
82
88
94
100
105
110
115
120
124
128
132
135
138
140
1
3
6
10
15
21
28
35
42
49
56
63
69
75
81
87
93
98
103
108
113
117
121
125
128
131
133
1
3
6
10
15
21
28
35
42
49
56
62
68
74
80
86
91
96
101
106
110
114
118
121
124
126
1
3
6
10
15
21
28
35
42
49
55
61
67
73...

result:

ok 406 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 5932kb

input:

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

output:

1
3
6
10
15
21
28
36
44
52
60
68
76
84
92
99
106
113
120
127
134
140
146
152
158
164
169
174
179
184
188
192
196
199
202
204
1
3
6
10
15
21
28
36
44
52
60
68
76
84
91
98
105
112
119
126
132
138
144
150
156
161
166
171
176
180
184
188
191
194
196
1
3
6
10
15
21
28
36
44
52
60
68
76
83
90
97
104
111
1...

result:

ok 666 lines

Test #9:

score: 0
Accepted
time: 1ms
memory: 5712kb

input:

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

output:

1
3
6
10
15
21
28
36
45
54
63
72
81
90
99
108
117
125
133
141
149
157
165
173
180
187
194
201
208
215
221
227
233
239
245
250
255
260
265
269
273
277
280
283
285
1
3
6
10
15
21
28
36
45
54
63
72
81
90
99
108
116
124
132
140
148
156
164
171
178
185
192
199
206
212
218
224
230
236
241
246
251
256
260
...

result:

ok 1035 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

100 100
31 92
16 73
42 62
11 38
42 99
81 95
27 97
11 89
6 60
15 85
14 27
55 84
42 88
38 47
20 54
52 61
55 79
77 95
57 92
61 95
63 81
8 38
67 91
8 13
27 59
27 41
15 37
15 46
46 100
21 88
19 47
76 98
13 29
4 72
12 97
4 30
13 53
32 84
23 93
66 69
54 74
77 95
77 92
80 92
44 62
19 64
4 75
30 51
37 60
70 ...

output:

595
595
171
171
378
630
231
153
3374
36
435
1804
1880
900
253
351
78
2227
36
1
2841
351
435
1225
1886
2725
990
2435
105
435
1484
45
45
1293
1653
3
1931
66
190
2900
171
2144
378
351
2115
406
300
900
1275
595
171
1880
378
690
861
91
2835
2473
120
1431
1569
1239
1587
1534
210
435
465
66
15
136
120
1326...

result:

ok 100 lines

Test #11:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

100 100
24 63
17 51
60 76
40 61
3 7
44 80
50 86
61 77
91 97
17 61
15 42
39 100
40 56
32 53
12 85
17 31
84 98
39 97
8 27
15 99
39 65
46 77
6 18
23 39
17 37
49 67
36 84
13 18
73 77
15 27
51 57
13 49
36 41
16 35
3 9
69 78
23 73
4 66
12 20
11 70
27 58
38 98
44 69
71 75
35 39
68 76
28 33
37 66
72 81
36 9...

output:

2187
1485
939
528
1176
2397
231
1378
630
2278
1035
55
1485
2760
378
2211
21
300
66
2701
253
1275
3191
190
703
6
10
2004
2285
3216
699
15
210
10
28
153
15
861
356
120
153
171
2908
1128
3306
450
1770
3088
630
1425
28
231
66
105
2346
276
1891
149
105
36
66
55
2465
468
666
465
2145
946
595
10
1945
210
2...

result:

ok 100 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 5688kb

input:

100 100
12 14
2 19
83 91
49 64
17 88
9 10
23 70
30 100
52 83
72 84
17 35
47 62
38 55
18 46
74 91
4 11
11 37
22 79
9 15
9 48
28 30
42 51
78 100
59 98
14 61
65 85
1 10
32 41
30 69
27 32
91 98
81 98
13 62
43 76
21 33
24 41
59 98
11 97
37 94
82 87
9 31
2 40
45 89
49 88
22 37
36 73
6 96
50 91
20 97
16 95...

output:

300
446
91
66
1077
609
822
1206
21
1396
325
1611
171
3
15
3
1147
78
3
66
752
527
1402
28
666
541
45
21
623
1683
1378
153
21
1050
1468
287
798
515
1548
654
879
136
435
276
153
1968
255
21
714
15
1496
91
1960
276
458
442
973
66
435
918
478
351
91
342
612
55
1
91
28
153
1266
10
1336
561
1380
253
6
136
...

result:

ok 100 lines

Test #13:

score: 0
Accepted
time: 1ms
memory: 7816kb

input:

100 100
41 90
17 72
51 92
11 22
33 47
33 92
2 58
42 95
14 94
28 31
13 66
45 71
7 44
87 91
82 98
18 23
55 74
7 58
59 88
7 95
57 76
7 97
65 86
61 67
4 71
3 12
16 18
44 55
59 65
34 61
31 90
1 28
50 74
78 90
8 19
9 48
16 95
20 81
78 87
23 91
9 20
6 37
58 83
62 86
36 91
21 55
30 88
5 8
47 56
4 5
34 71
34...

output:

15
2032
1480
1128
171
78
3033
1275
435
91
561
820
561
36
36
1810
28
1326
406
1077
1225
21
171
1
406
45
1378
190
66
1081
1980
28
136
6
1275
946
3
253
1686
120
78
946
10
45
741
120
45
231
438
1572
1225
15
1326
28
105
820
36
2413
10
435
210
21
10
820
435
2508
28
15
2694
6
465
190
2413
2319
15
6
10
3295...

result:

ok 100 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 5892kb

input:

100 100
9 14
28 88
35 36
63 74
18 38
40 44
38 61
16 94
19 23
17 74
94 95
49 59
25 86
41 42
80 82
74 79
38 49
19 28
1 73
8 24
13 32
15 29
68 73
40 73
64 85
30 56
36 40
30 98
3 64
12 45
72 87
9 66
77 81
74 99
14 30
61 63
48 58
30 78
28 56
52 68
78 82
11 82
36 93
4 83
19 27
1 14
8 81
22 68
43 87
30 62
...

output:

886
225
28
351
435
190
630
496
528
2013
6
10
36
3
630
45
276
1143
120
351
325
231
136
741
697
291
6
496
78
325
15
36
1302
120
3
3
1
2481
528
1176
561
6
561
276
465
435
28
190
136
613
961
55
45
2984
3
78
2152
6
1033
1281
171
253
1927
1
528
520
2798
528
1095
78
153
21
903
91
1326
325
630
2823
1705
138...

result:

ok 100 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

100 100
6 72
30 62
75 98
40 45
31 61
13 20
46 48
31 33
57 76
25 97
9 47
45 89
66 88
60 71
10 81
12 61
19 96
16 34
48 79
5 92
7 69
31 42
80 81
38 86
47 58
31 33
20 72
4 37
11 29
14 90
89 100
94 96
27 44
42 46
63 65
44 88
56 68
48 77
47 82
23 54
29 35
42 90
7 38
17 33
76 90
42 78
29 42
23 43
77 93
9 9...

output:

190
561
66
171
697
210
1551
630
36
3191
2071
78
990
15
1431
36
276
693
136
171
1657
837
1663
1378
21
406
136
3
171
528
2883
28
136
378
10
1653
325
2031
91
3471
171
45
1431
231
66
171
903
939
1
667
1228
695
1135
528
378
465
1830
1786
15
1566
120
2128
6
703
3026
36
435
2149
66
21
1128
630
3
10
21
1176...

result:

ok 100 lines

Test #16:

score: 0
Accepted
time: 1ms
memory: 7732kb

input:

100 100
61 82
16 58
15 70
47 48
11 56
71 84
15 90
37 96
60 70
2 50
48 91
31 45
3 91
15 21
35 51
12 37
47 71
41 73
24 30
16 23
45 49
18 21
21 41
2 43
52 61
25 65
18 93
75 83
1 66
14 35
47 90
66 95
18 97
19 33
66 91
21 53
52 64
35 52
40 60
32 41
43 84
5 35
4 84
2 61
37 97
85 90
4 94
10 92
36 85
29 73
...

output:

1348
741
1275
861
1275
171
703
2001
1685
435
66
276
1266
2613
561
2275
1413
3
561
666
1863
66
1011
78
1540
465
903
741
91
1081
435
21
1691
1063
528
406
1898
3
820
1128
1911
861
231
66
66
36
1176
528
136
1253
105
3
120
3142
2331
28
1225
91
91
2521
435
21
15
1985
3202
899
10
528
990
903
55
190
300
465...

result:

ok 100 lines

Test #17:

score: 0
Accepted
time: 1ms
memory: 5712kb

input:

100 100
40 66
7 28
16 78
40 66
29 88
25 46
55 76
8 53
54 98
49 82
4 28
30 71
33 37
75 87
51 66
17 28
75 84
71 73
40 81
40 86
15 96
47 61
30 96
17 42
23 40
73 91
48 65
6 13
12 88
83 100
40 62
76 94
27 96
13 52
15 37
64 84
24 61
24 33
51 83
30 44
9 70
41 47
41 86
33 100
79 97
10 14
37 63
92 97
63 85
2...

output:

253
406
120
10
1302
3069
66
105
780
1847
3
1
3
1711
253
2320
1378
28
1453
10
741
300
561
1
36
1791
276
1081
1176
36
66
171
276
1176
465
2484
66
3403
2453
741
325
2516
3
120
1445
666
2436
210
2985
190
136
2206
561
1162
780
36
231
1948
1794
36
2344
325
136
190
780
153
303
1792
253
21
990
231
231
2493
...

result:

ok 100 lines

Test #18:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

100 100
10 49
48 93
49 51
24 61
6 11
28 76
8 98
3 51
67 95
14 76
10 97
21 72
40 57
34 87
37 84
17 19
3 63
27 63
55 61
16 65
35 76
20 93
41 76
7 86
37 53
43 54
22 71
42 74
17 29
2 17
19 39
48 63
28 88
13 58
52 80
16 29
11 94
53 97
58 74
19 60
3 9
45 87
74 96
17 27
43 52
17 53
36 76
2 72
52 82
10 30
6...

output:

136
105
253
190
2038
3
45
3395
1
1766
1445
2360
190
136
1953
15
666
325
55
15
231
3
28
1326
820
666
946
3
91
1035
78
55
1169
78
1225
1
1378
820
136
6
1904
666
861
325
10
3
171
3
231
595
300
1946
1128
45
36
465
153
1176
1176
91
276
136
3
2319
21
325
300
820
3
1176
231
2584
276
15
171
406
780
231
741
...

result:

ok 100 lines

Test #19:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

100 100
31 48
24 36
47 82
85 100
46 59
66 94
15 64
17 83
21 37
35 42
47 86
21 41
31 44
31 41
10 70
16 50
85 94
33 61
39 54
39 92
6 67
83 91
58 98
56 59
22 89
9 68
30 80
55 64
78 100
54 86
4 10
14 43
44 67
41 93
19 79
31 57
18 47
9 64
41 90
66 95
7 44
61 80
33 70
18 31
36 70
14 94
23 96
16 25
12 55
3...

output:

91
351
1096
630
6
153
231
741
45
780
1936
2076
45
666
78
465
780
120
3601
45
595
1378
15
45
1128
231
2010
45
36
595
465
1971
1441
1726
1275
351
2076
36
903
190
120
1821
253
3265
36
3
666
10
253
1947
1378
300
1957
1528
1683
231
1128
171
990
3
1176
666
741
1791
171
91
1
351
378
630
300
1582
171
105
14...

result:

ok 100 lines

Test #20:

score: 0
Accepted
time: 1ms
memory: 5924kb

input:

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

output:

366
1698
762
714
3
758
550
78
2043
578
563
967
1720
446
377
102
6
1325
268
1274
342
1870
45
501
1572
362
234
217
104
767
316
158
28
1105
1820
1038
1216
415
2133
425
1304
349
351
713
153
1432
383
1150
1468
435
128
868
748
85
231
126
909
349
10
1984
2257
21
945
78
1345
560
791
1058
297
1287
359
167
16...

result:

ok 1000 lines

Test #21:

score: 0
Accepted
time: 0ms
memory: 5724kb

input:

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

output:

2946
105
2899
16361
16361
6279
12175
210
3269
4217
10048
2458
13937
1430
4264
10045
4016
10871
13610
7122
194
10368
9897
8788
15953
11088
8195
55
6025
15598
10513
5429
5840
10269
17826
16840
742
3503
3131
2151
330
1951
322
16701
280
3249
9234
546
370
19110
3757
12510
5612
6065
13805
3547
4745
19656
...

result:

ok 1000 lines

Test #22:

score: 0
Accepted
time: 0ms
memory: 7744kb

input:

60 1770
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
2 3
2...

output:

44968
8392
23706
20840
23382
51134
43582
11840
57240
8644
153
18113
3079
14956
22636
31614
30470
18876
29933
39685
26192
17709
105
44910
29458
1862
6457
16016
17926
41608
51910
6976
41011
11169
7628
41983
40064
11617
8558
37257
14417
54614
6256
4064
62134
41770
2768
31963
15953
32057
45404
16674
902...

result:

ok 1000 lines

Test #23:

score: 0
Accepted
time: 2ms
memory: 5732kb

input:

80 3160
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
...

output:

29685
148940
46252
528
7710
105429
162846
38868
37493
16794
17670
34300
91700
1258
106466
48926
4776
706
143150
161819
4251
49017
71884
351
54407
146981
117700
134679
127703
85399
93121
131348
15906
11566
14598
13311
155434
73354
37856
68452
11198
46333
25057
4922
58558
48727
18038
68056
68562
80144...

result:

ok 1000 lines

Test #24:

score: 0
Accepted
time: 25ms
memory: 5724kb

input:

100 4950
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

200805
78228
35308
101566
193878
208229
41972
69271
102295
32662
215084
129422
56761
142165
13454
117597
288754
14448
67545
54710
102255
9550
167479
137202
28041
39705
70625
174619
6562
76778
91153
7509
218684
15230
40366
60710
7704
3828
174052
21271
206436
60410
6822
158216
217634
98370
115958
1616...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 26ms
memory: 6124kb

input:

200 19900
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

output:

554732
1029283
2446815
1284896
386106
1976156
65799
614017
304900
96765
1647137
2443454
1396111
244344
804657
2398442
22596
56594
231861
733999
1529049
866152
700774
1482142
813216
12930
1290419
218094
1181498
898219
2274283
98070
1107356
1691327
521030
252057
1960512
914765
521804
1001994
1205622
1...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 34ms
memory: 6276kb

input:

300 44850
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

output:

1651512
3971957
3647411
2746873
11935
2044865
3068063
4038220
4415924
3131755
4030280
7260274
651554
6653849
1859737
5454728
724710
6406540
4743858
6293993
3477629
3920931
1862611
809695
4940658
4280975
101626
6112459
165094
1894639
6005868
310957
6323951
1309398
2634920
1292515
8335634
2339534
2153...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 37ms
memory: 6388kb

input:

400 79800
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

output:

13665992
18970874
2765411
641593
17366512
11842444
1350804
2752259
8262610
8375659
62872
4061346
9661849
3726202
10977922
13729769
7342746
266436
2517029
17558978
4390030
2850181
308730
8960277
8596255
4589033
1955290
7764510
4460096
9752665
1620110
5828355
3595757
15491909
3255877
7433669
12612914
...

result:

ok 100000 lines

Test #28:

score: 0
Accepted
time: 71ms
memory: 10084kb

input:

100000 99999
1 2
1 3
2 4
1 5
3 6
4 7
4 8
7 9
2 10
8 11
2 12
10 13
12 14
14 15
7 16
4 17
9 18
2 19
19 20
5 21
3 22
21 23
22 24
23 25
23 26
18 27
17 28
15 29
8 30
30 31
6 32
13 33
33 34
27 35
5 36
3 37
11 38
19 39
29 40
14 41
31 42
10 43
42 44
13 45
23 46
19 47
29 48
32 49
23 50
32 51
47 52
52 53
36 5...

output:

217559370
9058896
772972221
58574076
391062561
2901505753
61067826
2944935885
55067265
310590426
82799146
5653203
229440331
80994628
1883537376
126667486
864344253
535250121
179409153
1200965545
402753
2241903
1294260003
359106600
100642578
980159950
3256688865
1725751875
2265256
1272777831
12584893...

result:

ok 100000 lines

Test #29:

score: 0
Accepted
time: 71ms
memory: 8220kb

input:

100000 99999
1 2
1 3
3 4
4 5
1 6
2 7
3 8
7 9
5 10
3 11
8 12
8 13
11 14
9 15
10 16
15 17
3 18
13 19
10 20
7 21
14 22
2 23
4 24
6 25
22 26
18 27
3 28
16 29
11 30
27 31
4 32
2 33
18 34
10 35
30 36
17 37
19 38
5 39
19 40
24 41
30 42
38 43
22 44
28 45
27 46
4 47
21 48
10 49
38 50
29 51
40 52
18 53
46 54
...

output:

1491699510
1172746
614759580
94126060
2190789721
1606452903
936396
48644316
214876815
956309511
1186502541
24356710
369444153
88611328
399554046
99666021
235824903
49675528
2043231
31494016
27949026
22127878
1056551496
141952825
798061176
308003790
881055253
2151253621
1600337025
70846656
4091370111...

result:

ok 100000 lines

Test #30:

score: 0
Accepted
time: 69ms
memory: 10376kb

input:

100000 99999
1 2
1 3
3 4
1 5
2 6
4 7
2 8
3 9
8 10
7 11
7 12
4 13
13 14
9 15
13 16
5 17
5 18
10 19
11 20
12 21
15 22
8 23
6 24
21 25
15 26
11 27
24 28
21 29
27 30
27 31
22 32
4 33
16 34
11 35
6 36
28 37
12 38
26 39
29 40
23 41
35 42
7 43
43 44
3 45
29 46
20 47
19 48
48 49
3 50
13 51
20 52
42 53
40 54...

output:

224476266
206278516
5506221
424409545
360904411
19110
138919446
20215261
6288831
56972475
313964211
565269876
1239497155
761768028
1659945771
2442550671
288156021
307929336
49496275
1083009070
283517578
1318745046
2216880991
1300831521
213448791
70051366
2105064055
865134406
27531910
423070416
11791...

result:

ok 100000 lines

Test #31:

score: 0
Accepted
time: 67ms
memory: 10284kb

input:

100 100000
51 74
55 82
18 84
34 72
42 56
11 84
24 87
83 95
64 66
10 74
30 76
45 85
51 64
9 64
23 64
39 88
40 70
12 64
78 83
50 54
34 83
53 60
50 100
50 66
4 17
7 72
73 86
20 22
2 36
18 27
47 51
33 41
39 74
10 96
78 87
30 31
22 52
45 73
63 64
34 59
56 77
30 54
61 90
19 39
1 21
26 56
53 62
77 78
35 59...

output:

2077212
468211
2010375
370088
1550695
2099813
3800353
1228958
3238147
1014026
4018141
919308
634052
379788
6487
717773
158950
1943527
1887657
253655
3105260
267291
858148
59020
3472262
2246779
2859918
223219
3440352
513404
2152887
3628272
900883
2268461
216637
2798695
497556
1621597
78
1165399
27026...

result:

ok 100000 lines

Test #32:

score: 0
Accepted
time: 64ms
memory: 6712kb

input:

100 100000
80 98
15 87
48 75
54 56
12 87
50 68
11 35
38 74
20 89
48 55
27 87
22 88
93 100
53 80
34 69
56 94
12 64
29 63
4 87
65 100
60 90
15 97
15 84
16 79
14 55
19 63
62 81
31 91
14 36
13 79
34 94
26 64
31 42
18 48
9 97
32 50
37 58
4 32
40 67
63 90
55 100
8 37
7 35
14 48
1 39
7 26
11 59
12 98
25 58...

output:

728867
273521
69984
3363811
305998
605847
3008784
1310412
314113
305605
1576631
3805419
112733
2349279
215205
460010
1869732
287673
3951545
1115073
3006760
1783829
1198962
2701248
440153
1851184
2830505
2085534
2727765
48690
1593143
2850349
3710242
507725
304799
676738
2015503
2451549
1150683
146823...

result:

ok 100000 lines

Test #33:

score: 0
Accepted
time: 71ms
memory: 10544kb

input:

100 100000
22 60
31 89
42 88
19 54
27 88
34 61
36 77
32 77
81 96
42 55
31 92
20 43
10 64
10 46
6 53
3 45
4 15
33 43
41 81
38 95
41 68
62 90
63 93
26 39
20 63
29 47
7 19
18 92
54 100
33 37
24 32
4 56
39 82
9 59
27 95
47 71
35 81
76 93
52 64
38 85
18 93
42 62
8 20
16 84
2 100
60 82
14 57
86 90
37 64
5...

output:

332818
991492
574327
869552
763148
399673
225606
1819686
300638
2607608
141761
1124496
35440
279196
1223523
3474536
567830
2122406
473323
895530
1818608
882210
2842790
3033207
351224
2052122
401585
1948295
2086636
2023003
770257
1087616
137488
1044306
650352
3232624
1162949
219425
219865
3076801
166...

result:

ok 100000 lines

Test #34:

score: 0
Accepted
time: 68ms
memory: 10636kb

input:

100 100000
52 96
56 96
1 70
24 76
50 62
53 98
23 75
32 51
73 80
53 75
33 72
58 98
65 72
87 99
6 13
4 28
55 70
78 98
8 62
66 90
8 10
71 79
30 34
21 97
64 81
40 62
4 33
45 75
35 95
43 52
68 91
36 49
23 45
43 98
40 76
7 16
13 26
3 15
77 88
5 68
53 78
7 88
18 71
6 11
85 91
2 47
35 42
20 59
38 91
1 41
35...

output:

2830939
2252133
973964
380530
2411682
25633
1018066
1135282
2700470
3271890
679654
1090600
1619725
2320321
3935112
3008250
1524772
300386
375675
3758992
593214
151757
824309
1485647
1090206
1308622
1614203
2415688
2159393
2445495
3118091
3447239
1054673
474656
309558
1315466
2337318
1311326
805349
2...

result:

ok 100000 lines

Test #35:

score: 0
Accepted
time: 54ms
memory: 6700kb

input:

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

output:

4829022
3901887
211365
1223145
2433618
4227795
4267593
3389067
2189286
3403224
815661
2207304
4210371
2527272
8006625
4120182
2706165
441540
64944
2301354
4038111
2802096
6832188
88605
856251
1597563
3650328
457875
4714281
117018
2405205
1291554
921987
1035441
1329075
7895844
2163447
5387481
4209975...

result:

ok 100000 lines

Test #36:

score: 0
Accepted
time: 49ms
memory: 10036kb

input:

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

output:

821178
218130
23825151
2169828
21419559
17822160
18749232
2869128
13095891
17076906
16543440
41389569
70549380
8359632
50656293
81993924
29147823
27351621
34753212
61616322
23572404
21958020
8877114
24120855
45410544
8445546
17583399
4898097
24898077
13404582
22490487
59845095
7732260
9187803
342507...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 52ms
memory: 6884kb

input:

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

output:

338536143
283041693
656085
63243675
27561600
660233970
429497046
650444949
238756122
140355963
35208636
89491050
257774220
503129682
115138485
174472551
831136878
536646330
462693726
526187376
268863111
575322462
467853210
94120587
160153983
249595038
407359260
45950491
418478148
99080091
160683930
...

result:

ok 100000 lines

Test #38:

score: 0
Accepted
time: 43ms
memory: 6716kb

input:

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

output:

500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499
500499...

result:

ok 100000 lines

Test #39:

score: 0
Accepted
time: 49ms
memory: 6784kb

input:

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

output:

50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
50004999
500...

result:

ok 100000 lines

Test #40:

score: 0
Accepted
time: 42ms
memory: 10508kb

input:

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

output:

1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
1250024999
125...

result:

ok 100000 lines

Test #41:

score: 0
Accepted
time: 43ms
memory: 10092kb

input:

10000 100000
137 8569
8569 9959
2766 9959
2766 7849
5455 7849
5455 9877
146 9877
146 9787
5015 9787
988 5015
988 8083
6420 8083
6420 9235
4597 9235
3986 4597
3986 6819
6819 7520
4312 7520
4312 6768
2689 6768
2689 8419
2884 8419
2884 8464
8464 9805
7926 9805
4701 7926
2276 4701
2276 6834
2829 6834
28...

output:

500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
500586399
...

result:

ok 100000 lines

Test #42:

score: 0
Accepted
time: 46ms
memory: 7976kb

input:

100000 100000
2879 57954
30614 47722
4779 21359
2517 3803
6177 9269
4836 41850
58900 91309
3353 58336
5161 20586
78011 80924
35915 82825
27980 36533
24401 26668
6336 11454
69769 74191
71099 84611
44219 83286
55133 63467
12189 24077
26011 59034
25927 41016
35826 65953
42269 54528
11375 27390
5068 356...

output:

1
25425
101025
226801
402753
630003
906531
1233235
1610115
2037171
2516646
3044278
3622086
4250070
4931370
5659930
6438666
7267578
8146666
9080191
10059855
11089695
12169711
13299903
14485653
15716421
16997365
18328485
19716060
21147756
22629628
24161676
25743900
27383700
29066500
30799476
32582628
...

result:

ok 99681 lines

Test #43:

score: 0
Accepted
time: 47ms
memory: 10572kb

input:

100000 100000
38702 39963
51966 83499
69297 71710
22890 91656
23353 86496
14702 19554
4861 7228
23430 37781
57519 58447
40499 95217
20171 80648
8544 44172
20320 69256
2643 18031
10795 12873
76895 78593
16280 62282
9655 96695
4345 6160
18154 18181
61334 63323
20371 26724
42334 84788
10018 38865
11545...

output:

1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
1831139892
183...

result:

ok 100000 lines

Test #44:

score: 0
Accepted
time: 29ms
memory: 8420kb

input:

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

output:

5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
5000049999
500...

result:

ok 100000 lines

Test #45:

score: 0
Accepted
time: 47ms
memory: 6992kb

input:

10000 100000
137 8569
8569 9959
2766 9959
2766 7849
5455 7849
5455 9877
146 9877
146 9787
5015 9787
988 5015
988 8083
6420 8083
6420 9235
4597 9235
3986 4597
3986 6819
6819 7520
4312 7520
4312 6768
2689 6768
2689 8419
2884 8419
2884 8464
8464 9805
7926 9805
4701 7926
2276 4701
2276 6834
2829 6834
28...

output:

13926003
43897373
182384684
161916670
2543640
74426917
38944379
120276263
186616841
89828100
29275442
111035364
350501487
118427654
197584958
58585017
195982379
1152921
688551
2604903
81003
282255902
167091545
279364463
563391
70432343
2826253
88911540
142801996
1502511
2673828
212343375
37108746
17...

result:

ok 100000 lines
English 繁體中文 简体中文

伺服器時間: 2024-11-29 17:36:12 | 開源專案