QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498408#4071. Galactic Collegiate Programming ContestZhaoZiLongAC ✓89ms11060kbC++17869b2024-07-30 13:54:592024-07-30 13:55:00

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
2 7
3 5
1 6
1 9

output:

2
3
2
1

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 48ms
memory: 4744kb

input:

100000 100000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 60ms
memory: 4824kb

input:

100000 100000
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #4:

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

input:

100000 100000
5 1
1 1
1 1
2 1
1 1
2 1
4 1
4 1
1 1
4 1
1 1
2 1
1 1
2 1
3 1
5 1
1 1
2 1
1 1
1 1
2 1
2 1
1 1
3 1
3 1
5 1
3 1
1 1
2 1
1 1
2 1
5 1
4 1
4 1
4 1
4 1
2 1
2 1
3 1
5 1
2 1
3 1
3 1
3 1
5 1
1 1
3 1
3 1
1 1
3 1
1 1
2 1
5 1
5 1
3 1
4 1
3 1
3 1
2 1
4 1
3 1
2 1
1 1
2 1
1 1
4 1
1 1
3 1
2 1
1 1
4 1
4 ...

output:

2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
1
1
2
2
2
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 76ms
memory: 8780kb

input:

100000 100000
55327 1
99139 1
71762 1
29617 1
45413 1
25203 1
17598 1
12185 1
61815 1
34125 1
11875 1
42983 1
23226 1
83353 1
4102 1
36477 1
27664 1
30200 1
65341 1
7227 1
87024 1
88551 1
57914 1
17679 1
23141 1
29742 1
39939 1
21405 1
22572 1
91574 1
26588 1
30493 1
39818 1
48602 1
66761 1
6680 1
9...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 83ms
memory: 7224kb

input:

100000 100000
30482 1
76250 1
37507 1
1 1
1 1
32309 1
49333 1
1 1
1 1
10246 1
1 1
1 1
72682 1
55670 1
1 1
1 1
1 1
1 1
1 1
1 1
46963 1
50193 1
55133 1
1 1
1 1
32898 1
1 1
49168 1
1 1
1 1
36014 1
1 1
1 1
93437 1
37362 1
3615 1
1 1
55953 1
76473 1
40943 1
1 1
37810 1
88470 1
33197 1
31007 1
30194 1
1 1...

output:

2
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 72ms
memory: 4876kb

input:

100000 100000
2 1
5 1
2 1
4 1
3 1
3 1
4 1
5 1
3 1
1 1
2 1
5 1
1 1
1 1
1 1
3 1
2 1
3 1
1 1
1 1
3 1
3 1
3 1
3 1
5 1
2 1
5 1
2 1
2 1
3 1
2 1
1 1
1 1
4 1
4 1
4 1
2 1
1 1
4 1
1 1
3 1
3 1
2 1
3 1
3 1
1 1
2 1
2 1
5 1
4 1
1 1
3 1
3 1
4 1
4 1
1 1
2 1
5 1
2 1
5 1
5 1
2 1
5 1
3 1
4 1
2 1
3 1
1 1
3 1
2 1
1 1
5 ...

output:

2
3
3
4
5
5
5
5
5
5
5
5
4
1
1
1
1
2
1
1
1
2
2
2
2
2
2
2
3
3
3
3
2
2
2
2
3
2
2
1
2
2
2
2
2
2
2
3
3
3
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
2
2
2
2
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 48ms
memory: 4900kb

input:

100000 100000
1 666
1 150
1 487
1 597
1 829
1 60
1 770
1 531
1 659
1 522
1 52
1 988
1 406
1 553
1 609
1 683
1 824
1 758
1 128
1 915
1 577
1 430
1 35
1 794
1 36
1 865
1 524
1 336
1 580
1 280
1 727
1 238
1 800
1 932
1 562
1 84
1 327
1 997
1 783
1 200
1 376
1 537
1 826
1 929
1 213
1 759
1 799
1 640
1 2...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 62ms
memory: 4808kb

input:

100000 100000
2 524
2 826
2 52
2 268
2 191
2 212
2 425
2 351
2 565
2 136
2 510
2 259
2 499
2 578
2 308
2 84
2 363
2 449
2 257
2 140
2 50
2 175
2 640
2 878
2 703
2 207
2 583
2 653
2 657
2 75
2 190
2 781
2 421
2 505
2 110
2 71
2 677
2 824
2 219
2 287
2 365
2 647
2 110
2 173
2 683
2 590
2 884
2 883
2 9...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 89ms
memory: 4744kb

input:

100000 100000
4 575
4 298
1 21
2 149
3 865
5 379
5 503
5 330
1 642
3 704
1 228
5 582
3 63
3 605
1 101
3 810
3 160
4 390
2 802
2 650
5 649
3 335
2 953
4 381
2 651
5 331
5 881
5 183
1 554
2 211
1 504
4 959
3 590
2 517
3 873
2 41
3 8
3 162
1 331
1 411
1 688
5 301
1 827
5 169
5 723
4 455
3 633
1 27
4 92...

output:

2
2
2
2
2
2
3
3
2
2
1
2
2
3
1
2
2
2
2
2
3
3
3
3
4
4
4
4
3
4
3
3
3
4
4
4
4
4
4
2
2
2
2
2
3
3
3
2
2
3
3
3
2
2
2
2
3
3
3
3
3
4
4
4
4
4
4
4
4
2
3
3
3
4
4
4
2
2
2
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 78ms
memory: 8776kb

input:

100000 100000
13278 186
88538 976
46258 767
2370 544
62288 858
28296 292
1752 493
7261 783
41911 520
80625 965
95940 593
65666 690
26657 428
39906 604
79096 623
31158 272
86458 957
44963 561
96358 510
28646 213
35836 796
69889 442
76394 192
62381 118
32711 870
12138 288
49465 231
79986 625
52150 501...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #12:

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

input:

100000 100000
2041 678
56284 687
34509 604
16106 421
94039 894
97202 737
1 196
1 568
1 144
1 455
1 824
15933 639
73732 657
1 451
1 402
1 135
17685 914
18978 1
33265 705
1 647
1 259
74744 671
15424 559
1 300
1 510
25208 290
97158 728
39486 547
1 590
1203 559
1 394
1 92
1 150
1 866
1 487
68679 337
1 6...

output:

2
3
4
5
6
7
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 70ms
memory: 4876kb

input:

100000 100000
1 95
3 813
3 958
5 300
3 14
1 215
3 421
3 961
1 548
3 656
5 29
3 888
4 536
3 567
5 325
2 179
3 144
5 6
2 118
4 411
4 222
1 689
3 836
3 280
1 948
4 272
2 274
1 75
3 605
4 49
5 20
5 858
1 392
5 210
5 582
2 469
1 363
4 883
4 659
1 365
5 549
2 50
1 11
4 721
2 677
4 355
4 800
3 996
4 336
3 ...

output:

1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
3
2
3
3
3
3
3
3
2
3
3
2
2
2
2
2
2
3
3
2
2
2
2
2
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
4
5
5
4
...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 84ms
memory: 11060kb

input:

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

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 84ms
memory: 7276kb

input:

100000 100000
2 200
3 200
97957 5
4 200
63738 1
5 200
90629 1
54951 3
6 200
7 200
78402 9
8 200
27499 10
29986 8
9 200
10 200
11 200
12 200
71892 2
13 200
81128 4
14 200
93267 6
15 200
87278 6
16 200
17 200
72775 2
18 200
15817 8
19 200
82892 2
20 200
87150 6
64633 10
21 200
22 200
11804 8
23 200
69...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines