QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78335#4894. 学姐买瓜Pure_Furies50 263ms9976kbC++20895b2023-02-17 21:21:292023-02-17 21:21:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-17 21:21:30]
  • 评测
  • 测评结果：50
  • 用时：263ms
  • 内存：9976kb
查看
  • [2023-02-17 21:21:29]
  • 提交

answer

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
const int B=700;
int w[300003],f[300003],c[300003],q,n,W[300003],R[300003],G[300003];
int main(){
	ios::sync_with_stdio(0);
	cin>>q>>n;c[n]=-1;G[n]=n;
	for(int i=0;i<n;i+=B)
		for(int j=i;j<min(i+B,n);j++)
			c[j]=i,w[j]=n+1,W[j]=j,R[i]=j+1,G[i]=n;
	while(q--){
		int t,l,r;
		cin>>t>>l>>r;l--;
		if(t==1){
			w[l]=min(w[l],r);
			for(int i=l;~i&&c[i]==c[l];i--){
				w[i]=min(w[i],w[i+1]);
				if(c[w[i]]==c[i]){
					f[i]=f[w[i]]+1,
					W[i]=W[w[i]];
				}
				else
					W[i]=i;
			}for(int i=0;i<=l;i+=B)
				G[i]=min(G[i],r);
		}else{int a=0;
			while(l<n&&l<=r)
				if(W[l]!=l&&W[l]<=r)
					a+=f[l],l=W[l];
				else if(w[l]<=min(r,G[R[c[l]]]))
					a++,l=w[l];
				else l=R[c[l]];
			cout<<a<<'\n';
		}
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 3ms
memory: 7616kb

input:

11 13
2 4 4
1 11 12
1 1 5
1 2 3
1 2 10
2 2 8
1 6 6
2 2 10
1 6 11
2 2 3
2 2 13

output:

0
1
2
1
3

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 9ms
memory: 5420kb

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #3:

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

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #4:

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

input:

14 11
1 1 8
1 4 11
2 4 8
1 2 7
1 7 11
2 2 9
1 6 10
1 2 6
1 8 10
1 2 6
2 9 10
1 9 9
1 3 10
1 2 4

output:

0
1
0

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 18ms
memory: 5424kb

input:

2000 2000
1 1589 1640
1 1741 1765
2 191 1596
1 426 493
2 1434 1606
1 925 955
2 589 1148
2 1347 1608
2 686 1516
1 1535 1563
1 1835 1841
1 1513 1537
2 30 1710
2 123 171
2 1 2000
2 128 1310
2 270 879
1 1918 1941
2 965 1951
2 176 1452
1 1391 1421
1 614 664
2 1 2000
1 296 328
1 1378 1402
1 29 47
1 92 123...

output:

0
0
1
0
1
4
0
6
2
1
5
2
9
12
4
0
6
14
3
3
0
1
13
3
6
19
13
20
1
4
2
10
1
5
4
8
3
5
24
18
9
17
13
0
28
22
4
6
13
1
13
4
15
5
2
16
1
33
25
16
18
17
8
17
23
36
22
27
9
23
9
7
17
2
12
16
39
11
32
40
4
10
15
23
21
14
10
15
6
43
17
3
17
0
1
15
14
29
33
8
44
44
5
10
27
22
11
6
23
0
7
24
14
24
1
9
36
15
39
...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 7ms
memory: 7628kb

input:

2000 2000
1 1589 1640
1 1741 1765
2 191 1596
1 426 493
2 1434 1606
1 925 955
2 589 1148
2 1347 1608
2 686 1516
1 1535 1563
1 1835 1841
1 1513 1537
2 30 1710
2 123 171
2 1 2000
2 128 1310
2 270 879
1 1918 1941
2 965 1951
2 176 1452
1 1391 1421
1 614 664
2 1 2000
1 296 328
1 1378 1402
1 29 47
1 92 123...

output:

0
0
1
0
1
4
0
6
2
1
5
2
9
12
4
0
6
14
3
3
0
1
13
3
6
19
13
20
1
4
2
10
1
5
4
8
3
5
24
18
9
17
13
0
28
22
4
6
13
1
13
4
15
5
2
16
1
33
25
16
18
17
8
17
23
36
22
27
9
23
9
7
17
2
12
16
39
11
32
40
4
10
15
23
21
14
10
15
6
43
17
3
17
0
1
15
14
29
33
8
44
44
5
10
27
22
11
6
23
0
7
24
14
24
1
9
36
15
39
...

result:

ok 1000 lines

Test #7:

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

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #8:

score: 0
Accepted
time: 12ms
memory: 5412kb

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #9:

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

input:

2000 2000
2 100 273
1 1901 1904
2 51 958
2 731 1771
1 1772 1775
1 375 378
1 540 543
1 649 652
1 129 132
2 139 286
2 155 1490
2 87 1279
1 547 550
2 1135 1365
1 1685 1688
2 470 1269
2 1521 1540
2 62 634
2 1186 1668
1 1276 1279
1 725 728
2 1571 1599
1 246 249
2 243 681
1 103 106
1 547 550
2 324 361
2 5...

output:

0
0
0
0
3
4
0
3
0
4
0
0
5
0
6
1
8
0
2
1
11
3
1
5
15
6
1
18
1
5
0
1
4
22
8
5
24
17
8
26
0
6
27
4
17
14
29
3
40
15
30
23
13
6
13
10
18
2
33
9
31
47
12
0
48
4
27
2
3
10
6
52
15
1
17
7
9
58
15
7
9
37
17
2
27
4
13
57
32
21
43
66
16
49
10
6
0
26
25
51
42
13
26
5
82
4
82
13
14
13
5
48
8
38
94
15
23
3
39
38...

result:

ok 990 lines

Test #10:

score: 0
Accepted
time: 5ms
memory: 7484kb

input:

2000 2000
2 66 273
1 1 501
1 2 502
2 51 70
1 3 503
2 731 1771
1 4 504
2 149 1627
2 1792 1849
1 5 505
2 139 286
2 155 1490
2 87 1279
1 6 506
2 816 1365
2 576 783
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 7 507
1 8 508
1 9 509
2 1571 1599
1 10 510
2 1 2000
2 1 2000
2 1 2000
2 564 648
2 1215 1807...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result:

ok 1004 lines

Test #11:

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

input:

2000 2000
2 66 273
1 1 501
1 2 502
2 51 70
1 3 503
2 731 1771
1 4 504
2 149 1627
2 1792 1849
1 5 505
2 139 286
2 155 1490
2 87 1279
1 6 506
2 816 1365
2 576 783
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 7 507
1 8 508
1 9 509
2 1571 1599
1 10 510
2 1 2000
2 1 2000
2 1 2000
2 564 648
2 1215 1807...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
...

result:

ok 1004 lines

Test #12:

score: 0
Accepted
time: 6ms
memory: 5488kb

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

0
1
2
2
3
5
5
5
5
9
9
14
14
14
14
15
15
16
15
15
17
15
15
18
17
17
18
20
19
19
20
20
19
20
20
20
20
20
20
20
21
20
22
23
22
24
25
22
24
24
24
23
26
27
25
27
28
29
28
27
30
30
30
27
29
29
28
30
31
30
31
31
30
29
32
30
33
31
34
33
13
35
33
35
31
32
32
33
31
32
32
33
35
35
36
34
36
35
36
34
38
36
36
35...

result:

ok 1000 lines

Test #13:

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

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

0
1
2
2
3
5
5
5
5
9
9
14
14
14
14
15
15
16
15
15
17
15
15
18
17
17
18
20
19
19
20
20
19
20
20
20
20
20
20
20
21
20
22
23
22
24
25
22
24
24
24
23
26
27
25
27
28
29
28
27
30
30
30
27
29
29
28
30
31
30
31
31
30
29
32
30
33
31
34
33
13
35
33
35
31
32
32
33
31
32
32
33
35
35
36
34
36
35
36
34
38
36
36
35...

result:

ok 1000 lines

Test #14:

score: 0
Accepted
time: 10ms
memory: 7480kb

input:

2000 2000
2 87 1924
1 1223 1268
2 64 1968
1 426 493
2 27 1931
1 1191 1226
2 86 1985
1 1742 1771
2 81 1984
1 631 677
1 792 813
2 32 1936
2 63 1954
2 56 1952
2 4 1937
1 1095 1117
1 781 797
1 1036 1052
1 144 174
1 999 1027
2 43 1911
2 49 1995
1 326 363
1 1580 1627
1 270 303
1 1010 1037
1 687 728
1 1895...

output:

0
1
2
2
3
5
5
5
5
9
9
14
14
14
14
15
15
16
15
15
17
15
15
18
17
17
18
20
19
19
20
20
19
20
20
20
20
20
20
20
21
20
22
23
22
24
25
22
24
24
24
23
26
27
25
27
28
29
28
27
30
30
30
27
29
29
28
30
31
30
31
31
30
29
32
30
33
31
34
33
13
35
33
35
31
32
32
33
31
32
32
33
35
35
36
34
36
35
36
34
38
36
36
35...

result:

ok 1000 lines

Test #15:

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

input:

12 11
2 4 5
2 2 10
1 3 7
1 4 7
1 5 11
1 5 7
2 1 3
1 1 4
2 3 3
2 11 11
1 1 10
2 10 11

output:

0
0
0
0
0
0

result:

ok 6 lines

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #16:

score: 30
Accepted
time: 166ms
memory: 9812kb

input:

80000 80000
2 14017 46708
2 26100 26240
2 3855 12007
2 72192 75052
1 12615 30948
2 36 51149
1 47528 79363
1 68506 72310
1 31635 62123
2 7480 77998
1 52530 75803
2 1793 30290
2 47012 72210
1 63304 66834
1 24988 62161
1 34585 61735
1 2973 61060
2 23879 44146
2 11903 26606
2 11536 72847
1 47874 65933
1...

output:

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

result:

ok 39967 lines

Test #17:

score: 0
Accepted
time: 180ms
memory: 8072kb

input:

80000 80000
2 2861 34160
2 8759 15795
2 7885 64470
2 54605 64108
2 34678 46289
1 77858 79250
1 31975 45909
2 41585 66397
2 670 8018
2 21646 77764
2 59388 66346
2 11547 33881
1 33641 65830
1 20381 76117
2 1 80000
1 21230 50809
2 1 80000
2 62738 76613
1 5547 74063
1 12843 34869
1 58364 70930
2 1 80000...

output:

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

result:

ok 40238 lines

Test #18:

score: 0
Accepted
time: 169ms
memory: 8040kb

input:

80000 80000
2 2861 34160
2 8759 15795
2 7885 64470
2 54605 64108
2 34678 46289
1 77858 79250
1 31975 45909
2 41585 66397
2 670 8018
2 21646 77764
2 59388 66346
2 11547 33881
1 33641 65830
1 20381 76117
2 1 80000
1 21230 50809
2 1 80000
2 62738 76613
1 5547 74063
1 12843 34869
1 58364 70930
2 1 80000...

output:

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

result:

ok 40238 lines

Test #19:

score: 0
Accepted
time: 155ms
memory: 8332kb

input:

80000 80000
2 18977 66117
2 1 80000
2 27578 46739
2 30830 62244
2 55697 71643
2 27378 65022
1 56047 56096
2 49937 56489
2 45072 77388
2 44709 55212
1 37844 37869
2 36378 69188
1 74387 74409
2 1 80000
2 1 80000
1 1432 1471
2 64369 67027
1 24704 24715
2 4643 31966
1 35276 35326
2 7090 54798
2 25675 78...

output:

0
0
0
0
0
0
1
1
0
2
3
3
0
1
3
4
1
1
2
3
2
3
7
3
7
13
9
5
6
10
1
18
14
8
2
4
7
7
25
3
5
13
17
4
20
11
4
37
16
22
26
1
16
12
14
20
7
7
12
4
6
20
2
22
49
43
14
22
29
49
21
19
15
37
31
27
12
41
64
0
64
14
4
41
26
41
42
7
16
17
22
83
7
50
0
66
26
6
46
7
9
75
64
18
100
28
45
101
9
87
10
30
109
60
111
42
3...

result:

ok 40000 lines

Test #20:

score: 0
Accepted
time: 150ms
memory: 8328kb

input:

80000 80000
2 67953 77105
2 24204 57828
1 32435 32451
1 72390 72515
2 1 80000
1 32015 32040
2 6622 24973
2 24454 72822
1 64442 64452
1 70875 70909
2 45452 73012
1 20698 20722
2 10641 20426
2 11766 32138
1 27388 27408
1 16905 16931
1 76806 76814
1 39565 39589
2 16827 78470
2 36042 54665
1 27305 27318...

output:

0
0
2
0
3
3
0
2
10
1
6
14
4
1
10
9
0
2
4
2
11
0
11
6
12
11
7
2
2
0
20
11
1
3
29
0
9
19
30
30
17
2
3
16
29
5
0
11
18
9
20
22
6
2
6
22
11
4
19
51
4
21
56
24
27
0
16
3
3
6
8
4
19
29
54
5
35
63
20
70
22
11
43
8
39
19
3
83
18
4
40
7
59
7
27
25
1
21
11
24
16
25
44
19
25
39
39
30
15
19
57
47
57
114
86
30
5...

result:

ok 40000 lines

Test #21:

score: 0
Accepted
time: 210ms
memory: 8080kb

input:

80000 80000
2 67953 77105
2 24204 57828
1 32435 32451
1 72390 72515
2 1 80000
1 32015 32040
2 6622 24973
2 24454 72822
1 64442 64452
1 70875 70909
2 45452 73012
1 20698 20722
2 10641 20426
2 11766 32138
1 27388 27408
1 16905 16931
1 76806 76814
1 39565 39589
2 16827 78470
2 36042 54665
1 27305 27318...

output:

0
0
2
0
3
3
0
2
10
1
6
14
4
1
10
9
0
2
4
2
11
0
11
6
12
11
7
2
2
0
20
11
1
3
29
0
9
19
30
30
17
2
3
16
29
5
0
11
18
9
20
22
6
2
6
22
11
4
19
51
4
21
56
24
27
0
16
3
3
6
8
4
19
29
54
5
35
63
20
70
22
11
43
8
39
19
3
83
18
4
40
7
59
7
27
25
1
21
11
24
16
25
44
19
25
39
39
30
15
19
57
47
57
114
86
30
5...

result:

ok 40000 lines

Test #22:

score: 0
Accepted
time: 209ms
memory: 8080kb

input:

80000 80000
2 50698 64950
1 79547 79547
2 4065 38573
2 5409 32899
1 9328 9328
2 24681 34436
2 2364 64359
2 27664 56147
2 1 80000
2 1 80000
2 17386 30575
1 53323 53323
1 77467 77467
1 39684 39684
1 48202 48202
1 46370 46370
2 16758 76161
1 68737 68737
2 14967 35344
2 21887 51637
1 39740 39740
2 11908...

output:

0
0
0
0
1
0
2
2
0
4
0
3
7
4
5
4
2
1
14
13
16
8
3
7
1
16
13
22
25
8
8
3
18
11
15
0
32
7
1
0
20
4
1
4
20
49
1
6
4
4
11
2
50
31
52
27
10
29
12
55
27
6
28
6
0
40
19
62
12
36
36
22
7
37
48
36
31
9
12
4
88
2
50
89
9
8
13
89
22
92
1
17
75
82
13
64
44
43
52
102
50
46
2
17
63
41
21
78
21
0
115
48
20
7
8
117
...

result:

ok 39991 lines

Test #23:

score: 0
Accepted
time: 194ms
memory: 9976kb

input:

80000 80000
1 47823 47827
2 51702 74055
2 1 80000
1 75249 75253
2 33942 52215
2 236 78066
1 46733 46737
2 4477 54423
2 4537 73268
1 11123 11127
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 3969 3973
1 51839 51843
1 26475 26479
2 38789 69975
2 57669 71418
2 44434 69847
1 55243 55247
2 67...

output:

0
1
1
2
2
2
2
2
0
1
3
0
3
1
2
10
0
10
2
2
1
1
2
2
7
7
9
22
0
16
8
15
6
10
32
11
9
15
33
4
19
4
8
5
3
39
1
39
12
25
1
3
12
29
2
57
1
35
28
37
32
0
47
2
71
41
22
43
12
61
24
3
78
39
46
42
24
53
83
11
19
6
11
26
43
25
44
39
76
19
59
19
94
7
14
13
35
15
1
51
24
1
9
21
19
42
34
18
8
0
4
106
44
46
25
3
7
...

result:

ok 39870 lines

Test #24:

score: 0
Accepted
time: 167ms
memory: 9824kb

input:

80000 80000
1 47823 47827
2 51702 74055
2 1 80000
1 75249 75253
2 33942 52215
2 236 78066
1 46733 46737
2 4477 54423
2 4537 73268
1 11123 11127
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 3969 3973
1 51839 51843
1 26475 26479
2 38789 69975
2 57669 71418
2 44434 69847
1 55243 55247
2 67...

output:

0
1
1
2
2
2
2
2
0
1
3
0
3
1
2
10
0
10
2
2
1
1
2
2
7
7
9
22
0
16
8
15
6
10
32
11
9
15
33
4
19
4
8
5
3
39
1
39
12
25
1
3
12
29
2
57
1
35
28
37
32
0
47
2
71
41
22
43
12
61
24
3
78
39
46
42
24
53
83
11
19
6
11
26
43
25
44
39
76
19
59
19
94
7
14
13
35
15
1
51
24
1
9
21
19
42
34
18
8
0
4
106
44
46
25
3
7
...

result:

ok 39870 lines

Test #25:

score: 0
Accepted
time: 170ms
memory: 8280kb

input:

80000 80000
1 1 20001
1 2 20002
1 3 20003
2 51702 74055
2 1 80000
1 4 20004
1 5 20005
2 33942 52215
2 236 78066
1 6 20006
1 7 20007
2 4477 54423
2 4537 73268
1 8 20008
1 9 20009
2 31028 53255
2 37333 69221
2 18137 29907
2 56088 79239
1 10 20010
1 11 20011
1 12 20012
1 13 20013
1 14 20014
1 15 20015
...

output:

0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
...

result:

ok 40000 lines

Test #26:

score: 0
Accepted
time: 131ms
memory: 8348kb

input:

80000 80000
1 1 20001
1 2 20002
2 50644 76906
2 41744 45216
2 57575 75408
2 12225 61676
1 3 20003
1 4 20004
1 5 20005
1 6 20006
1 7 20007
1 8 20008
1 9 20009
1 10 20010
1 11 20011
2 24858 75983
1 12 20012
2 1 80000
1 13 20013
2 22970 48447
1 14 20014
1 15 20015
2 66927 77660
2 24937 39575
2 53299 55...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
...

result:

ok 40008 lines

Test #27:

score: 0
Accepted
time: 220ms
memory: 8164kb

input:

80000 80000
1 18629 18651
1 45305 45395
1 73500 73529
2 79 79950
2 42 79979
1 3060 3093
1 7620 7697
1 23250 23317
1 8916 8933
1 42381 42392
2 50 79962
2 63 79988
2 1 79999
1 44186 44204
1 64397 64461
1 75722 75761
2 51 79932
2 40 79950
2 48025 50108
1 15925 15949
1 63914 63932
2 24 79988
2 89 79942
...

output:

3
3
8
8
8
11
11
0
13
13
16
20
21
24
28
30
30
30
30
30
31
33
34
34
35
37
40
40
40
40
40
43
43
44
50
50
51
51
52
52
52
53
55
58
59
60
60
61
61
61
66
66
66
66
67
69
70
70
71
76
76
78
79
79
79
81
81
81
83
83
32
83
83
88
88
91
94
94
94
94
96
98
98
98
98
98
98
102
103
103
105
105
105
107
108
109
109
111
1...

result:

ok 40000 lines

Test #28:

score: 0
Accepted
time: 203ms
memory: 8244kb

input:

80000 80000
1 18629 18651
1 45305 45395
1 73500 73529
2 79 79950
2 42 79979
1 3060 3093
1 7620 7697
1 23250 23317
1 8916 8933
1 42381 42392
2 50 79962
2 63 79988
2 1 79999
1 44186 44204
1 64397 64461
1 75722 75761
2 51 79932
2 40 79950
2 48025 50108
1 15925 15949
1 63914 63932
2 24 79988
2 89 79942
...

output:

3
3
8
8
8
11
11
0
13
13
16
20
21
24
28
30
30
30
30
30
31
33
34
34
35
37
40
40
40
40
40
43
43
44
50
50
51
51
52
52
52
53
55
58
59
60
60
61
61
61
66
66
66
66
67
69
70
70
71
76
76
78
79
79
79
81
81
81
83
83
32
83
83
88
88
91
94
94
94
94
96
98
98
98
98
98
98
102
103
103
105
105
105
107
108
109
109
111
1...

result:

ok 40000 lines

Test #29:

score: 0
Accepted
time: 263ms
memory: 9564kb

input:

80000 80000
1 40636 40641
1 69847 69873
1 16352 16422
1 52522 52614
2 38 79981
2 63 79902
1 30452 30467
2 47 79984
2 63 79953
1 71760 71824
2 28 79921
2 57 79987
2 15 79919
2 78 79901
2 55 79901
1 40610 40625
1 20412 20465
1 58984 59018
1 45311 45324
1 27428 27445
1 59989 60027
1 53348 53410
1 6426 ...

output:

4
4
5
5
6
6
6
6
6
14
15
15
16
17
17
18
19
20
20
20
20
22
22
22
22
22
22
25
25
27
28
28
30
32
32
37
37
38
42
42
44
48
49
49
53
53
53
57
57
61
62
62
65
67
67
67
67
67
67
67
67
67
67
67
67
76
77
78
78
78
79
79
81
83
84
84
87
87
88
88
88
88
92
95
96
99
100
100
103
103
104
104
106
106
107
109
112
112
116...

result:

ok 40000 lines

Test #30:

score: 0
Accepted
time: 197ms
memory: 8184kb

input:

80000 80000
1 40636 40641
1 69847 69873
1 16352 16422
1 52522 52614
2 38 79981
2 63 79902
1 30452 30467
2 47 79984
2 63 79953
1 71760 71824
2 28 79921
2 57 79987
2 15 79919
2 78 79901
2 55 79901
1 40610 40625
1 20412 20465
1 58984 59018
1 45311 45324
1 27428 27445
1 59989 60027
1 53348 53410
1 6426 ...

output:

4
4
5
5
6
6
6
6
6
14
15
15
16
17
17
18
19
20
20
20
20
22
22
22
22
22
22
25
25
27
28
28
30
32
32
37
37
38
42
42
44
48
49
49
53
53
53
57
57
61
62
62
65
67
67
67
67
67
67
67
67
67
67
67
67
76
77
78
78
78
79
79
81
83
84
84
87
87
88
88
88
88
92
95
96
99
100
100
103
103
104
104
106
106
107
109
112
112
116...

result:

ok 40000 lines

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #31:

score: 0
Time Limit Exceeded

input:

300000 300000
1 65058 175646
2 84915 100033
2 1 300000
1 4571 84453
2 229719 237569
1 145712 164438
2 95823 98589
1 130465 255002
1 63938 79365
2 16862 171297
2 108832 182624
1 88047 160443
1 24866 238717
2 49449 260305
1 116709 221422
1 65757 236100
1 2820 37609
2 85634 174637
1 4878 66462
1 121731...

output:

0
1
0
0
2
1
2
1
2
4
0
0
2
0
2
0
0
1
6
0
1
3
2
0
1
2
2
1
0
4
0
1
4
1
1
2
3
2
2
2
1
0
5
1
1
3
5
1
0
1
0
0
2
0
2
7
0
3
0
0
2
0
3
4
2
4
3
0
8
2
1
7
6
2
2
4
2
0
6
0
8
7
6
1
2
0
9
9
0
4
10
9
2
5
2
2
6
1
7
10
1
2
5
4
5
6
7
1
10
5
7
5
2
2
1
5
5
0
3
5
7
1
2
7
0
1
10
2
8
6
6
4
7
1
0
5
11
0
0
10
11
5
5
3
0
11
...

result:
English 繁體中文 简体中文

Server Time: 2024-11-30 10:44:33 | OpenSource Project