QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387266#8196. Zapobiegliwy studentjames1BadCreeper100 ✓145ms14148kbC++141.9kb2024-04-12 11:22:262024-04-12 11:22:27

Judging History

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

  • [2024-04-12 11:22:27]
  • 评测
  • 测评结果:100
  • 用时:145ms
  • 内存:14148kb
  • [2024-04-12 11:22:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 

int n; 
int a[N], b[N], id[N], c[N], an[N];  

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i], id[i] = i; 
    sort(id + 1, id + n + 1, [&](int x, int y) { return b[x] < b[y]; }); 
    int lst = 0, ans = 0; 
    for (int i = 1; i <= n; ++i) {
        
        int x = id[i]; 
        // cout << a[x] << " " << b[x] << "\n"; 
        if (a[x] >= lst) lst = b[x], ++ans, c[x] = 1; 
    }
    // return 0; 
    lst = 0; 
    int cnt = 0, flg = 1, dot = 0; 
    for (int i = 1, r = 0, tmp = 0; i <= n; ++i) {
        int x = id[i]; 
        if (a[x] >= lst) {
            if (tmp && b[tmp] > a[x]) {
                an[x] = tmp; tmp = 0; ++dot; 
                r = lst = b[x]; 
                continue; 
            }
            ++i; 
            while (i <= n) {
                int y = id[i]; 
                if (a[y] < b[x] && a[y] >= r) { an[x] = y; break; } // 不能和真实值相交
                ++i; 
            }
            if (!an[x]) { flg = 0; break; }
            // cerr << a[x] << " " << b[x] << " " << a[an[x]] << " " << b[an[x]] << "\n"; 
            ++dot; 
            lst = b[an[x]]; r = b[x]; 
            // cerr << i << " " << lst << "\n"; 
        } else {
            if (a[x] >= r)
                tmp = x; 
        }
    }
    // return 0; 
    // cerr << dot << "\n"; 
    if (dot == ans) {
        cout << ans << '\n'; 
        for (int i = 1; i <= n; ++i)
            if (an[i]) cout << i << " " << an[i] << "\n"; 
        return 0; 
    }
    cout << ans - 1 << '\n'; 
    vector<int> p; 
    for (int i = 1; i <= n; ++i) if (c[i]) p.push_back(i); 
    for (int i = 0; i < int(p.size() - 1); ++i)
        cout << p[i] << " " << p.back() << "\n"; 
    return 0;
}

详细

Subtask #1:

score: 40
Accepted

Test #1:

score: 40
Accepted
time: 0ms
memory: 12032kb

input:

3000
3933353 70882522
431257009 431260553
90739306 181374877
122022862 131964741
563835356 563924377
118764371 334063455
26214655 62023860
40797538 289373132
85278264 154263043
559290951 559390997
140863766 181337311
30550198 99872053
53298927 164507323
398655954 398779690
454048567 454187653
256862...

output:

710
2 2993
5 2993
10 2993
14 2993
15 2993
18 2993
19 2993
21 2993
24 2993
28 2993
35 2993
47 2993
48 2993
53 2993
55 2993
64 2993
70 2993
76 2993
83 2993
84 2993
87 2993
94 2993
98 2993
99 2993
102 2993
108 2993
112 2993
114 2993
115 2993
118 2993
129 2993
132 2993
134 2993
151 2993
161 2993
163 299...

result:

ok 

Test #2:

score: 40
Accepted
time: 0ms
memory: 11812kb

input:

3000
31030527 224953096
362558018 362950530
181784096 231354294
102853306 170479486
157957286 258809455
39420753 102841775
66680992 91375920
115393779 157957286
41333976 56861640
57405250 109915816
12325647 126099987
60106250 108557797
419465371 419502618
54901708 81479964
157718826 157957286
318294...

output:

1164
2 3000
13 3000
15 3000
16 3000
17 3000
18 3000
19 3000
26 3000
34 3000
36 3000
39 3000
46 3000
47 3000
49 3000
55 3000
56 3000
57 3000
60 3000
63 3000
64 3000
66 3000
67 3000
71 3000
73 3000
74 3000
79 3000
83 3000
85 3000
86 3000
89 3000
92 3000
95 3000
99 3000
100 3000
101 3000
108 3000
115 3...

result:

ok 

Test #3:

score: 40
Accepted
time: 2ms
memory: 11804kb

input:

3000
71012996 71094087
142103791 142153359
129250374 138842795
18535894 18554386
192995012 193103066
46363241 46370290
149525178 149638179
154963002 171398581
109691836 123828530
153720609 153864248
52639958 52757141
188195177 205887265
63643341 63689591
72539758 72605349
201057807 217241469
1334440...

output:

889
2 3000
4 3000
6 3000
7 3000
11 3000
13 3000
14 3000
20 3000
25 3000
26 3000
27 3000
32 3000
36 3000
40 3000
45 3000
53 3000
56 3000
62 3000
64 3000
72 3000
73 3000
74 3000
75 3000
76 3000
80 3000
87 3000
88 3000
91 3000
93 3000
97 3000
99 3000
100 3000
101 3000
107 3000
114 3000
118 3000
123 300...

result:

ok 

Test #4:

score: 40
Accepted
time: 0ms
memory: 11788kb

input:

3000
74523187 74639447
69002241 74017833
38903521 53274148
27964195 28108909
90480259 90714386
80227337 80233197
74024120 74355868
87997733 91873572
115068358 115237960
81118691 82016815
71587720 71686990
54665074 79252306
83590436 83831492
101758617 102092854
11897307 12018869
83749552 83831331
775...

output:

950
1 3000
4 3000
6 3000
9 3000
15 3000
16 3000
18 3000
24 3000
29 3000
31 3000
34 3000
36 3000
38 3000
42 3000
44 3000
45 3000
49 3000
52 3000
57 3000
59 3000
60 3000
63 3000
65 3000
66 3000
67 3000
68 3000
69 3000
78 3000
79 3000
82 3000
83 3000
84 3000
87 3000
90 3000
92 3000
95 3000
96 3000
98 3...

result:

ok 

Test #5:

score: 40
Accepted
time: 2ms
memory: 11796kb

input:

3000
7051210 8589811
18502361 18548147
10825587 10925453
10814101 11820256
6634997 7192161
8159514 9623111
6343123 9208117
11598681 13563271
15947954 16110829
11889628 11939148
8237287 8288595
18548147 18620522
9481884 10648149
8589811 8719610
11820256 11855114
14689173 16361212
10814101 10825530
65...

output:

196
15 2990
27 2990
34 2990
60 2990
72 2990
84 2990
96 2990
108 2990
176 2990
194 2990
213 2990
219 2990
256 2990
271 2990
284 2990
286 2990
323 2990
351 2990
356 2990
406 2990
408 2990
409 2990
411 2990
446 2990
449 2990
453 2990
458 2990
461 2990
466 2990
489 2990
498 2990
511 2990
513 2990
514 29...

result:

ok 

Test #6:

score: 40
Accepted
time: 0ms
memory: 12088kb

input:

3000
9666113 9699478
6965840 7841200
10055382 12219484
10288891 10367080
6969527 7162495
8594370 9548407
10250084 10288891
10420507 10762472
10055382 10123746
12068744 12162702
6969527 7162495
898461 1193510
12945038 12957489
8815357 8915885
10762472 10764220
11051606 11190103
10250084 10288891
1076...

output:

97
1 2979
9 2979
30 2979
76 2979
78 2979
119 2979
127 2979
236 2979
248 2979
287 2979
292 2979
341 2979
355 2979
361 2979
424 2979
448 2979
527 2979
539 2979
554 2979
648 2979
675 2979
684 2979
698 2979
783 2979
798 2979
823 2979
826 2979
831 2979
939 2979
967 2979
1062 2979
1077 2979
1078 2979
1079...

result:

ok 

Test #7:

score: 40
Accepted
time: 2ms
memory: 11868kb

input:

2990
50340082 121213456
3227228 116175285
424744925 424887740
31439322 277401622
336388021 336431031
15931482 29319341
75260985 231708778
185165107 185293971
67367703 141831559
17406456 49981991
49079607 445176184
94084419 94416531
265132826 265169936
107853545 320822230
62144003 123579437
377801615...

output:

989
3 2989
5 2989
8 2989
12 2989
13 2989
16 2989
17 2989
20 2989
22 2989
23 2989
27 2989
29 2989
30 2989
31 2989
33 2989
35 2989
36 2989
39 2989
41 2989
44 2989
46 2989
49 2989
53 2989
60 2989
66 2989
68 2989
69 2989
70 2989
73 2989
77 2989
78 2989
79 2989
82 2989
84 2989
85 2989
94 2989
95 2989
98 ...

result:

ok 

Test #8:

score: 40
Accepted
time: 2ms
memory: 12108kb

input:

2990
250865254 250869884
286482343 431381520
67327525 67430639
51403719 51487566
289528053 289582672
423899248 490004400
258417153 458191427
461265317 465980729
394370749 491254041
403746044 408137448
290547180 290680587
319179787 323134772
223102834 223331806
432432647 436809367
213343887 357836802...

output:

1182
1 2990
3 2990
4 2990
5 2990
11 2990
13 2990
16 2990
19 2990
23 2990
25 2990
26 2990
27 2990
29 2990
31 2990
32 2990
35 2990
45 2990
48 2990
52 2990
59 2990
61 2990
66 2990
67 2990
71 2990
73 2990
76 2990
77 2990
79 2990
80 2990
81 2990
86 2990
88 2990
89 2990
90 2990
94 2990
95 2990
96 2990
99 ...

result:

ok 

Test #9:

score: 40
Accepted
time: 2ms
memory: 11864kb

input:

2990
102788330 102925405
4878515 31638048
177455671 177533043
32255571 37544098
114232867 117557314
40689737 40719674
73751698 73933892
133909722 134297030
110647842 113985076
93078823 93091503
82870304 101468113
69527427 87652872
92822371 92926747
35890864 97925062
232144359 232402208
93726776 9656...

output:

813
3 2990
6 2990
8 2990
10 2990
15 2990
17 2990
29 2990
30 2990
40 2990
41 2990
43 2990
51 2990
53 2990
54 2990
56 2990
59 2990
61 2990
63 2990
66 2990
71 2990
74 2990
75 2990
76 2990
81 2990
84 2990
90 2990
93 2990
98 2990
108 2990
109 2990
111 2990
114 2990
121 2990
122 2990
123 2990
124 2990
125...

result:

ok 

Test #10:

score: 40
Accepted
time: 0ms
memory: 12096kb

input:

2990
35883857 36839641
17782252 51143143
68716248 76021874
76043743 76217639
33446237 33518833
39879049 41955106
44893112 73888169
38705671 40125877
53703222 64069313
60894195 61523325
25303122 25500733
37162379 45358432
10932450 11196880
33952191 34106194
86352421 87513151
21744478 28830372
8093553...

output:

714
4 2990
10 2990
11 2990
13 2990
22 2990
23 2990
30 2990
31 2990
34 2990
44 2990
47 2990
52 2990
54 2990
57 2990
60 2990
63 2990
65 2990
68 2990
87 2990
95 2990
100 2990
110 2990
114 2990
122 2990
133 2990
140 2990
142 2990
144 2990
155 2990
157 2990
173 2990
176 2990
182 2990
188 2990
190 2990
19...

result:

ok 

Test #11:

score: 40
Accepted
time: 1ms
memory: 11736kb

input:

2990
15071564 16374160
14115610 15457074
18513886 18574399
16420710 16483561
14783931 15042254
12820856 13241099
14794431 15774071
20604285 20741904
8954839 8981274
13733211 13972852
11879070 14016942
19228344 21918959
23906126 24094967
11863974 11949391
18459398 18770708
14783931 15101427
12478133 ...

output:

214
9 2989
23 2989
24 2989
61 2989
92 2989
118 2989
119 2989
145 2989
146 2989
161 2989
168 2989
205 2989
239 2989
264 2989
267 2989
280 2989
294 2989
295 2989
337 2989
350 2989
351 2989
353 2989
394 2989
424 2989
425 2989
429 2989
439 2989
452 2989
456 2989
457 2989
482 2989
498 2989
520 2989
529 2...

result:

ok 

Test #12:

score: 40
Accepted
time: 1ms
memory: 11744kb

input:

2990
5940513 5985963
7319348 7434051
6644317 6874055
7206754 9269298
9652129 9752692
4832948 5795408
5910136 6545830
9752692 9773617
6644317 7434051
5116164 5365823
8410392 8568019
5116164 6874055
5985963 5998318
2093281 2454423
9218895 9269298
5795408 5796544
5795408 5796544
6545830 6644317
5940513...

output:

90
39 2986
62 2986
78 2986
123 2986
138 2986
144 2986
147 2986
157 2986
170 2986
198 2986
215 2986
222 2986
226 2986
282 2986
283 2986
284 2986
297 2986
319 2986
325 2986
327 2986
522 2986
546 2986
550 2986
567 2986
588 2986
609 2986
688 2986
725 2986
743 2986
830 2986
850 2986
983 2986
1032 2986
10...

result:

ok 

Test #13:

score: 40
Accepted
time: 0ms
memory: 11852kb

input:

1910
75202538 75470705
121439276 121919190
251206481 252242944
86382123 92860960
614158821 614579149
305272572 305846919
646930494 647247261
130693374 131191622
57240909 57310488
625780955 628286239
44326730 44369315
171865307 172643196
44326730 44895004
429513780 430793052
563643413 564501483
16883...

output:

711
2 270
6 1105
7 222
8 970
11 13
12 1238
19 1613
20 537
24 1586
27 1663
31 1344
37 775
43 1837
48 1497
52 1299
55 112
58 1129
60 977
67 1707
68 261
75 267
77 1741
82 1389
85 1329
87 867
88 1690
89 1178
90 1143
91 691
93 62
96 1001
97 1503
98 1255
101 552
102 1400
103 1485
108 1146
109 1287
110 639...

result:

ok 

Test #14:

score: 40
Accepted
time: 1ms
memory: 11800kb

input:

1898
184900554 185195808
596932543 597022839
135894103 136382082
254770095 255722821
628780718 629396361
89010691 89162557
642069578 643306766
229707657 230831841
274813298 276499996
135062542 136833638
204166458 206497511
683486146 685362282
149063878 149102082
229267785 230703363
72612168 73087843...

output:

708
8 14
13 1825
18 1883
19 497
21 772
24 1
36 319
37 217
38 140
40 758
41 1082
45 873
47 464
49 146
51 148
54 1179
55 870
56 541
58 3
68 521
73 1125
74 424
78 1567
82 1139
83 519
84 1312
87 566
88 1391
90 6
94 686
103 971
105 589
110 1709
111 1086
114 483
116 1769
119 1242
120 1388
122 946
123 364
...

result:

ok 

Test #15:

score: 40
Accepted
time: 1ms
memory: 12012kb

input:

1868
738941544 739319851
22325451 23612100
253148693 253538781
545244471 546518034
312379559 315502647
249862738 250436819
527886214 529214868
261028713 274340180
558238279 558989089
592442191 592639859
88075311 89041265
317641731 340661240
499536929 500333273
510190160 510669948
517022124 517833793...

output:

680
1 1691
10 375
15 54
18 558
20 1685
21 966
23 1652
24 1821
28 1225
29 1846
32 1810
34 448
39 481
42 1625
43 1351
44 1052
46 695
47 141
49 997
51 1437
52 1013
58 1215
60 1462
61 1246
64 25
66 127
69 217
77 1077
84 1757
85 1508
88 1383
89 508
93 1233
99 420
100 1705
104 555
105 526
107 906
111 94
1...

result:

ok 

Test #16:

score: 40
Accepted
time: 0ms
memory: 12060kb

input:

1898
593691572 593906544
419361221 419442981
731410217 731573761
19426567 25770341
7209560 7370309
177180275 178264189
456333304 456650631
276969920 280173683
53912270 54256982
328109128 328601378
309178445 309374144
422353313 422624521
101935776 102094019
738549151 738791815
353088558 354042200
585...

output:

697
1 77
7 1619
10 1028
11 1583
13 631
16 560
17 1782
21 1736
24 601
25 1640
30 1065
31 1851
34 898
35 396
39 1075
41 449
49 890
51 1791
55 925
59 1699
63 1544
64 1242
66 628
67 1144
68 492
81 372
84 200
85 429
86 426
92 9
93 1459
94 1826
95 1240
96 273
100 28
101 1093
103 515
106 1046
108 241
110 4...

result:

ok 

Test #17:

score: 40
Accepted
time: 1ms
memory: 11788kb

input:

1844
102448427 104401885
10812012 11147082
420064916 421813703
661768204 662311317
508103199 511664791
442978839 443498253
241119414 241242725
396935383 397076925
580250057 580771846
432700109 433367374
646020379 646247214
29751892 30362447
37993837 44589226
709057845 716237087
359343035 374738552
4...

output:

674
7 856
9 930
12 1677
16 34
17 1122
18 226
21 1550
25 488
28 897
36 1118
42 467
44 1134
53 1638
65 1397
70 481
71 265
72 645
74 677
75 1116
76 545
77 1171
79 689
82 588
84 1211
87 1262
88 600
90 1283
91 472
95 1740
97 538
100 181
105 535
107 1800
108 1223
118 1668
119 737
120 31
121 1058
123 1164
...

result:

ok 

Test #18:

score: 40
Accepted
time: 1ms
memory: 11828kb

input:

1889
564785915 566122852
519698913 520739863
435185494 435314066
645242669 645599840
28210897 28439640
593709195 593719822
565773316 566216270
519871611 521349793
378541513 425804871
578073871 578784796
48330689 48551496
604868766 604875993
138704249 138722239
38415541 39737338
230466551 231577842
7...

output:

697
3 340
4 1081
5 1761
6 1525
7 1
11 943
12 73
13 849
19 189
24 704
27 1130
30 628
31 894
34 876
35 94
37 82
38 196
40 1249
44 412
47 994
48 378
50 64
54 435
57 515
60 232
65 1051
68 1524
71 667
72 1778
75 1506
80 887
83 1319
84 301
85 930
88 1700
96 480
101 1282
103 624
104 1604
109 959
112 363
11...

result:

ok 

Test #19:

score: 40
Accepted
time: 0ms
memory: 9832kb

input:

3000
924 2077
3806 3807
3479 3480
3061 3062
1205 1796
1351 1650
495 2506
4363 4364
4040 4041
4420 4421
957 2044
3885 3886
1315 1686
794 2207
3509 3510
3151 3152
4254 4255
3830 3831
1385 1616
748 2253
3121 3122
579 2422
623 2378
3645 3646
1484 1517
32 2969
439 2562
3210 3211
4183 4184
3683 3684
3598 ...

output:

1500
2 3000
3 3000
4 3000
8 3000
9 3000
10 3000
12 3000
15 3000
16 3000
17 3000
18 3000
21 3000
24 3000
28 3000
29 3000
30 3000
31 3000
35 3000
38 3000
41 3000
43 3000
44 3000
45 3000
46 3000
48 3000
53 3000
54 3000
60 3000
63 3000
65 3000
70 3000
72 3000
73 3000
75 3000
76 3000
79 3000
80 3000
82 3...

result:

ok 

Test #20:

score: 40
Accepted
time: 0ms
memory: 9732kb

input:

2
1 4
2 3

output:

1
2 1

result:

ok 

Test #21:

score: 40
Accepted
time: 1ms
memory: 11812kb

input:

2
1 2
3 4

output:

1
1 2

result:

ok 

Test #22:

score: 40
Accepted
time: 2ms
memory: 12112kb

input:

3000
65358258 65908047
385965515 386042234
37731087 38183736
299401409 300119156
454768183 454951855
312689188 312965778
304032771 304164881
217183822 217316878
174450942 174542630
451680500 452256646
75963152 76196904
86254155 86565208
40119130 40279303
370158759 370442706
396706744 397157378
30651...

output:

1499
1 3000
2 3000
5 3000
6 3000
8 3000
9 3000
10 3000
12 3000
13 3000
14 3000
15 3000
16 3000
17 3000
18 3000
20 3000
21 3000
23 3000
25 3000
30 3000
34 3000
36 3000
37 3000
40 3000
41 3000
43 3000
44 3000
47 3000
49 3000
50 3000
51 3000
52 3000
56 3000
58 3000
60 3000
61 3000
62 3000
63 3000
66 30...

result:

ok 

Subtask #2:

score: 60
Accepted

Dependency #1:

100%
Accepted

Test #23:

score: 60
Accepted
time: 138ms
memory: 13280kb

input:

500000
407892396 407894065
654503489 654503501
9066405 84391111
140987019 171563436
14057278 19781051
34941076 145785516
234766009 234766141
20335659 44712015
336459606 336460578
317292502 317292578
13283779 15008155
6484755 100390340
465647488 465647776
381908371 381910825
102485960 185427558
76325...

output:

254096
1 499999
2 499999
7 499999
9 499999
10 499999
13 499999
14 499999
19 499999
20 499999
21 499999
29 499999
30 499999
31 499999
32 499999
33 499999
36 499999
37 499999
42 499999
43 499999
44 499999
45 499999
46 499999
50 499999
52 499999
53 499999
54 499999
55 499999
58 499999
59 499999
61 4999...

result:

ok 

Test #24:

score: 60
Accepted
time: 115ms
memory: 12936kb

input:

500000
13002946 68701866
4733539 43995294
31492413 103830172
170770666 171815325
12805604 155553070
73232678 89080638
122151560 122802318
121601488 122265567
98532673 245103395
23340940 81165159
404593991 404594275
130046140 150732609
48079081 245423481
478588967 478589353
34762052 141554385
6826022...

output:

123907
11 500000
14 500000
17 500000
21 500000
22 500000
24 500000
33 500000
35 500000
39 500000
41 500000
46 500000
47 500000
56 500000
58 500000
59 500000
64 500000
82 500000
86 500000
88 500000
90 500000
97 500000
98 500000
104 500000
105 500000
106 500000
111 500000
112 500000
117 500000
118 500...

result:

ok 

Test #25:

score: 60
Accepted
time: 115ms
memory: 13584kb

input:

500000
26643253 26762939
124973874 124973924
104836056 139539875
95035682 101884314
107671424 114521776
105444682 105444834
46748925 46867583
41225663 63736637
177953802 177958013
149360101 159964168
145683623 155425562
41865427 41988301
107339428 114192197
192436713 192436745
77497028 79907719
2318...

output:

107589
2 499999
6 499999
9 499999
14 499999
16 499999
26 499999
33 499999
34 499999
35 499999
39 499999
41 499999
42 499999
45 499999
48 499999
52 499999
56 499999
58 499999
65 499999
70 499999
74 499999
84 499999
87 499999
91 499999
94 499999
96 499999
99 499999
108 499999
115 499999
116 499999
118...

result:

ok 

Test #26:

score: 60
Accepted
time: 113ms
memory: 13680kb

input:

500000
61971783 62075841
66131430 66132218
56238154 56238690
70076915 70077077
38011798 49115996
86388430 86388721
50785655 51197023
66314821 66335131
35347975 35348446
41895585 41924952
56721852 56721957
54523356 54571508
64943486 64943599
83965472 83965737
73610011 73748884
17824907 53135985
77041...

output:

109835
4 500000
9 500000
11 500000
17 500000
23 500000
34 500000
38 500000
50 500000
53 500000
57 500000
70 500000
71 500000
77 500000
79 500000
80 500000
90 500000
99 500000
120 500000
121 500000
123 500000
138 500000
139 500000
142 500000
146 500000
150 500000
151 500000
154 500000
155 500000
163 ...

result:

ok 

Test #27:

score: 60
Accepted
time: 94ms
memory: 13412kb

input:

500000
549476 1024522
829710 830282
415118 417693
900627 900646
612307 612794
425978 1066159
225433 225749
536172 676316
681207 681756
1493301 1493744
970766 972749
669865 1121461
1232252 1234410
772478 848691
1292705 1294653
645110 645345
555103 831576
1290503 1291102
1289304 1294653
63538 294731
4...

output:

2633
77 499999
154 499999
169 499999
256 499999
291 499999
301 499999
513 499999
633 499999
758 499999
832 499999
921 499999
1165 499999
1351 499999
2017 499999
2037 499999
2349 499999
2514 499999
2578 499999
2814 499999
3069 499999
3181 499999
3646 499999
3803 499999
4337 499999
4641 499999
4682 49...

result:

ok 

Test #28:

score: 60
Accepted
time: 71ms
memory: 12008kb

input:

500000
59055 59158
34450 35028
60662 60881
34182 34450
34450 39260
50981 51138
59055 59158
49699 52035
41744 41887
57978 58874
35028 41887
41887 42178
36810 53188
52355 53188
57793 57978
32988 33087
38381 42178
41697 41744
51138 51327
34182 41697
32286 38661
36602 47074
36810 37022
51327 52035
49699...

output:

115
4569 498149
12065 498149
12369 498149
16898 498149
17591 498149
23352 498149
24540 498149
28119 498149
28725 498149
30993 498149
31203 498149
31697 498149
42427 498149
44287 498149
46223 498149
54653 498149
60726 498149
71873 498149
72346 498149
73088 498149
76463 498149
82819 498149
85804 49814...

result:

ok 

Test #29:

score: 60
Accepted
time: 145ms
memory: 13536kb

input:

499990
948742631 949003988
768464404 768464571
384190932 384193353
80112927 80114309
589096347 589097682
70759321 70760675
28970784 28971152
394499087 394499682
683566590 683568937
209192916 209193238
392085104 392085884
371213970 371215503
891551959 891552951
389814151 389814198
352166345 352167268...

output:

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

result:

ok 

Test #30:

score: 60
Accepted
time: 109ms
memory: 13524kb

input:

499990
429148896 429151777
8193013 218244899
219266522 219639868
4219530 37374453
106959371 107228024
99134307 99404667
143400334 143687917
41398062 88930525
82381795 114350328
32011271 125545161
72448978 216170891
88734159 117405370
87545495 201886821
471444790 471445433
13307185 64810927
166753731...

output:

136999
1 499966
14 499966
17 499966
18 499966
24 499966
29 499966
31 499966
33 499966
38 499966
43 499966
44 499966
46 499966
47 499966
50 499966
51 499966
52 499966
56 499966
64 499966
65 499966
73 499966
74 499966
79 499966
88 499966
89 499966
90 499966
96 499966
107 499966
110 499966
112 499966
1...

result:

ok 

Test #31:

score: 60
Accepted
time: 118ms
memory: 14148kb

input:

499990
23315946 27579365
40128118 40129415
122201100 122436620
156057106 156395362
5745239 24364747
15207076 15207801
84025083 84027386
210395536 210396027
39041366 39041750
109300727 109405655
131326726 131583213
131727123 131727805
42081188 46459629
165678828 165678937
91300895 91301245
112722726 ...

output:

193921
2 499988
6 499988
7 499988
8 499988
9 499988
12 499988
14 499988
15 499988
16 499988
17 499988
20 499988
21 499988
26 499988
31 499988
33 499988
34 499988
41 499988
46 499988
48 499988
49 499988
55 499988
59 499988
63 499988
69 499988
79 499988
83 499988
84 499988
85 499988
87 499988
88 49998...

result:

ok 

Test #32:

score: 60
Accepted
time: 113ms
memory: 13596kb

input:

499990
19455659 49619275
52349364 52350224
3529937 19390686
17301372 45920111
20272556 35225907
61461723 62247708
46884837 47695311
92020790 92023872
94218595 94219721
59105993 72668879
78211271 78211555
1544311 2791589
94958034 94958055
35529888 47505235
7271832 7272908
63636409 63637185
83764915 8...

output:

74447
9 499986
11 499986
19 499986
27 499986
56 499986
72 499986
81 499986
87 499986
94 499986
102 499986
122 499986
137 499986
151 499986
156 499986
162 499986
199 499986
200 499986
222 499986
226 499986
227 499986
232 499986
236 499986
262 499986
272 499986
288 499986
300 499986
303 499986
317 499...

result:

ok 

Test #33:

score: 60
Accepted
time: 84ms
memory: 13380kb

input:

499990
1151472 1152459
593018 594473
289315 788469
168692 237090
903501 904065
248851 249454
845938 846960
634849 911812
296612 697067
430952 431473
1146908 1147314
686201 686275
713130 781179
679476 845874
945092 945517
235256 295919
285724 285728
470234 584188
163959 237783
172934 272433
350474 35...

output:

2703
179 499977
199 499977
238 499977
590 499977
757 499977
823 499977
911 499977
997 499977
1380 499977
1384 499977
1782 499977
1885 499977
1987 499977
2150 499977
2527 499977
2723 499977
2989 499977
3598 499977
4007 499977
4053 499977
4076 499977
4182 499977
4185 499977
4410 499977
4526 499977
474...

result:

ok 

Test #34:

score: 60
Accepted
time: 70ms
memory: 11876kb

input:

499990
57043 61353
61827 62133
74447 74553
57185 57707
53474 56355
53474 54680
39723 41557
38262 55213
59832 61282
61353 61827
50045 56355
49221 53141
41557 48901
48901 49221
50930 57185
62794 63258
50045 50062
13991 15757
58756 58961
51322 52678
50045 50062
53474 54680
53474 54680
51322 55213
55213...

output:

116
3134 499362
15738 499362
17707 499362
22900 499362
23351 499362
23582 499362
25411 499362
29845 499362
40201 499362
45492 499362
45959 499362
47807 499362
49016 499362
64937 499362
64961 499362
72922 499362
87606 499362
87774 499362
89551 499362
92793 499362
104602 499362
107400 499362
114197 49...

result:

ok 

Test #35:

score: 60
Accepted
time: 74ms
memory: 12944kb

input:

314300
524197415 524210323
496787896 496793207
82238259 82238773
251533834 251535738
662752628 662756074
305708987 305710968
553082058 553810952
426801990 427316637
700885978 700889113
324634315 324637427
172597379 172608941
621945256 621949200
689378341 689378842
590173930 590240692
204585773 20458...

output:

115875
1 162206
2 20436
3 220964
4 63235
6 223510
9 167265
13 252394
16 69904
19 60309
22 279763
24 284595
26 192151
29 269148
30 177085
34 215006
38 308756
40 4558
42 137093
44 266464
48 54945
50 193736
51 136635
52 123163
55 239099
56 215780
58 300443
60 204891
61 125061
62 181432
65 51441
66 2941...

result:

ok 

Test #36:

score: 60
Accepted
time: 79ms
memory: 12596kb

input:

314891
313105072 313170057
87030149 87030975
229859890 229863423
732365163 732366171
357433917 357445674
35469970 35470819
172235014 172240393
650294966 650296073
131063544 131157054
739570398 739621168
499910260 499914127
639003360 639004212
224364032 224364999
201227273 201240314
562437749 5624382...

output:

115983
6 194273
11 20342
12 127569
13 307046
15 94860
16 163963
17 127162
18 184042
27 215661
32 93851
33 83763
42 166639
43 242466
48 243960
49 237688
53 177009
54 305935
57 46720
58 277371
61 223304
62 69125
63 19308
66 18415
67 36186
71 244920
75 146247
84 214224
85 216031
86 66026
87 149781
90 1...

result:

ok 

Test #37:

score: 60
Accepted
time: 79ms
memory: 13072kb

input:

313988
371199163 371214227
393965363 393965725
709122126 709127065
475663022 475665087
233764642 233764949
326625060 326629570
374334307 374340009
342871007 342871349
75596724 75603086
4391767 4391826
230091427 230100616
371989094 371991773
288609870 288612889
13547924 13551501
441364388 441369905
7...

output:

115630
2 5060
8 218281
10 311957
14 166510
15 196772
20 280051
24 95363
25 177288
26 259054
34 239517
36 247625
40 293409
42 121636
47 255014
50 85063
54 215570
55 58205
56 217750
57 145481
60 27256
62 284768
65 163703
66 311671
70 184683
73 8661
85 7233
87 3451
88 51482
89 109455
94 246826
95 4441
...

result:

ok 

Test #38:

score: 60
Accepted
time: 77ms
memory: 12896kb

input:

314720
127910026 127915340
44213788 44221005
415670340 415680822
267281528 267326436
662014024 662015886
79675208 79723878
419407728 419416799
312926269 312939470
642030849 642039591
705170049 705175015
651863414 651865844
660584439 660671580
756898987 756909683
554710169 554711107
504664750 5046772...

output:

116002
5 232757
14 60135
17 95258
20 82710
21 104439
23 298347
25 125115
26 273643
27 124263
28 124871
29 313365
31 129963
32 246991
36 117305
37 309556
40 16132
43 138196
45 293822
49 61236
50 132893
52 66150
54 14042
55 153428
56 92320
57 83759
60 278619
63 297208
67 82340
68 279636
72 301711
77 1...

result:

ok 

Test #39:

score: 60
Accepted
time: 78ms
memory: 12136kb

input:

314720
347052617 347055339
724335968 724338799
750657412 750658553
615943191 615948897
663480371 663480534
439021379 439031125
201335524 201336439
713978966 713980236
69216691 69217406
303017614 303021225
350670549 350674031
215332258 215341384
45162666 45166153
423902103 423903988
429147104 4291483...

output:

115948
3 98454
6 52597
7 270248
8 122026
9 250729
11 193892
13 64071
15 26361
20 93674
23 17217
27 111718
28 25007
31 108079
36 259627
37 6438
39 106082
40 35773
41 65275
45 270739
46 169007
47 234527
48 36624
51 227730
52 187915
61 195811
62 251312
63 11262
65 142013
66 212333
68 145007
69 102823
7...

result:

ok 

Test #40:

score: 60
Accepted
time: 76ms
memory: 11924kb

input:

314447
679834604 679834918
658898707 658902690
371281102 371419988
108638749 108639370
728623301 728676550
148515084 148519334
383249460 383249917
688976425 688988953
246712312 246758901
324468223 324632740
215454415 215457585
324225156 324292922
716083076 716191643
148316304 148326023
467091813 467...

output:

115900
2 102233
4 149972
7 79689
11 72808
21 205498
22 87378
24 160251
25 44560
29 26747
32 267166
42 78411
45 149678
46 229603
50 232737
51 256447
52 206006
53 253275
55 204907
56 19490
58 312791
59 221532
60 240348
62 15578
63 210389
65 148136
66 82203
67 122639
70 275083
72 186992
73 191553
75 13...

result:

ok 

Test #41:

score: 60
Accepted
time: 123ms
memory: 12908kb

input:

500000
663930 663931
181262 318739
155097 344904
529821 529822
249900 250101
139591 360410
576099 576100
718720 718721
695797 695798
191707 308294
50250 449751
547024 547025
3527 496474
113290 386711
37128 462873
7336 492665
155485 344516
17961 482040
641728 641729
686672 686673
142381 357620
749763...

output:

250000
1 500000
4 500000
7 500000
8 500000
9 500000
12 500000
19 500000
20 500000
22 500000
26 500000
31 500000
35 500000
36 500000
38 500000
40 500000
41 500000
50 500000
53 500000
55 500000
59 500000
60 500000
62 500000
63 500000
65 500000
69 500000
70 500000
71 500000
73 500000
78 500000
80 50000...

result:

ok 

Test #42:

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

input:

2
1 4
2 3

output:

1
2 1

result:

ok 

Test #43:

score: 60
Accepted
time: 1ms
memory: 9728kb

input:

2
1 2
3 4

output:

1
1 2

result:

ok 

Test #44:

score: 60
Accepted
time: 129ms
memory: 14072kb

input:

500000
334052756 334053121
3441473 3441605
235556626 235557202
224036358 224037627
168105326 168106795
2918751 2919905
296780188 296781094
417453734 417454217
358680743 358685659
10891367 10892114
72332955 72333855
304396338 304397913
453299019 453301641
452531125 452531586
226391530 226394485
28647...

output:

249999
1 500000
5 500000
13 500000
15 500000
16 500000
17 500000
18 500000
21 500000
25 500000
26 500000
27 500000
29 500000
30 500000
31 500000
33 500000
34 500000
35 500000
36 500000
37 500000
38 500000
39 500000
40 500000
42 500000
44 500000
45 500000
46 500000
47 500000
48 500000
53 500000
58 50...

result:

ok 

Extra Test:

score: 0
Extra Test Passed