QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624339#8649. Escape Route 2hhoppitree14 521ms862208kbC++172.7kb2024-10-09 15:35:242024-10-09 15:35:24

Judging History

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

  • [2024-10-09 15:35:24]
  • 评测
  • 测评结果:14
  • 用时:521ms
  • 内存:862208kb
  • [2024-10-09 15:35:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int tl[N], tr[N], nxt[N], Vnxt[N];
pair<int, int> nd[N];
int Nxt[N][400], BIGNxt[N][400];
long long VNxt[N][400], BIGVNxt[N][400];

signed main() {
    int n, T, tot; scanf("%d%d", &n, &T);
    for (int i = 1, x; i < n; ++i) {
        scanf("%d", &x);
        tl[i] = tot + 1, tr[i] = tot + x;
        for (int j = 1; j <= x; ++j) {
            ++tot;
            scanf("%d%d", &nd[tot].first, &nd[tot].second);
        }
    }
    int sz = sqrt(n);
    for (int i = 1; i + 1 < n; ++i) {
        vector< pair< pair<int, int>, int> > o;
        pair<int, int> mn = {T + 1, 0};
        for (int j = tl[i + 1]; j <= tr[i + 1]; ++j) {
            o.push_back({nd[j], j});
            mn = min(mn, {nd[j].second, j});
        }
        sort(o.begin(), o.end());
        vector< pair<int, int> > to;
        for (int j = tl[i]; j <= tr[i]; ++j) {
            to.push_back({nd[j].second, j});
        }
        sort(to.begin(), to.end());
        for (int i = (int)to.size() - 1, j = (int)o.size() - 1, tv = T + 1, wh = 0; ~i; --i) {
            while (~j && o[j].first.first >= to[i].first) {
                if (o[j].first.second < tv) {
                    tv = o[j].first.second, wh = o[j].second;
                }
                --j;
            }
            if (tv <= T) nxt[to[i].second] = wh, Vnxt[to[i].second] = tv - to[i].first;
            else nxt[to[i].second] = mn.second, Vnxt[to[i].second] = T - to[i].first + mn.first;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        Nxt[i][0] = i;
        for (int j = 1; j <= sz; ++j) {
            Nxt[i][j] = nxt[Nxt[i][j - 1]];
            VNxt[i][j] = VNxt[i][j - 1] + Vnxt[Nxt[i][j - 1]];
        }
        BIGNxt[i][0] = i, BIGNxt[i][1] = Nxt[i][sz], BIGVNxt[i][1] = VNxt[i][sz];
    }
    for (int i = 1; i <= tot; ++i) {
        for (int j = 2; j <= sz + 1; ++j) {
            BIGNxt[i][j] = BIGNxt[BIGNxt[i][j - 1]][1];
            BIGVNxt[i][j] = BIGVNxt[i][j - 1] + BIGVNxt[BIGNxt[i][j - 1]][1];
        }
    }
    int q; scanf("%d", &q);
    map< pair<int, int>, long long> M;
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        if (M.count({l, r})) {
            printf("%lld\n", M[{l, r}]);
            continue;
        }
        long long res = 1e18;
        int step = r - l - 1;
        for (int i = tl[l]; i <= tr[l]; ++i) {
            long long S = nd[i].second - nd[i].first;
            int now = i;
            S += VNxt[now][step % sz] + BIGVNxt[Nxt[now][step % sz]][step / sz];
            res = min(res, S);
        }
        printf("%lld\n", M[{l, r}] = res);
    }
    return 0;
}

詳細信息

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 39ms
memory: 10556kb

input:

2 1000000000
1
359893566 955414858
300000
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 ...

output:

595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
...

result:

ok 300000 lines

Test #2:

score: 6
Accepted
time: 161ms
memory: 36972kb

input:

1384 702597566
1
93593482 288383752
1
483624997 516514674
1
217174776 378882844
1
381889032 694179867
1
143192510 343368096
1
20552425 654877612
1
34995000 223673833
1
86047336 507288111
1
58193455 564074888
1
543118270 579455813
1
42236607 257802041
1
244371899 634806939
1
173261583 634917538
1
245...

output:

152061320763
364193581975
101659406868
515885206553
273965799122
114948644944
78108129814
549857539900
166576516139
266640269522
36194858709
249707922175
12419530470
164111155048
607789899481
370597406072
100093371327
351888389540
72528927782
102643452509
26254171517
335577444460
126061743618
214062...

result:

ok 235294 lines

Test #3:

score: 6
Accepted
time: 196ms
memory: 49620kb

input:

2000 1000000000
1
251243678 591560449
1
994358883 999558886
1
322667352 514836853
1
538977337 603533309
1
249401760 363153703
1
104249966 416969473
1
103160611 933539967
1
300026318 706474995
1
637853185 969624295
1
612852422 686323121
1
890842468 964096005
1
127364216 656085651
1
565856726 79766828...

output:

804591361552
615732551026
616673957607
255388778080
246824759617
250452018635
3920166700
411598001493
191141891280
437294118321
839203030077
237616086785
395724762439
24493946848
261496520138
440921377339
879523097721
632991245786
629587780307
208737211703
514022647807
1235201434706
1239644739996
51...

result:

ok 300000 lines

Test #4:

score: 6
Accepted
time: 165ms
memory: 43584kb

input:

2000 702597566
1
234199188 250686543
1
187177414 485066634
1
187177414 584601655
1
187177414 584601655
1
472618361 588604455
1
619085294 688959957
1
619085294 661784753
1
218487968 619085294
1
619085294 642882128
1
260718505 642882128
1
599405824 642882128
1
609069701 699150927
1
609069701 702336507...

output:

1015957000190
680210081647
1242056863771
237697116977
4956604203
134440244240
408395990203
826647972707
545108473847
444013368984
460270771687
398420505294
739873557581
11886903864
782516902871
622468211441
160076268243
501156545599
68094738139
94221928973
846316719734
79740931643
53785803546
225843...

result:

ok 235294 lines

Test #5:

score: 6
Accepted
time: 204ms
memory: 49472kb

input:

2000 1000000000
1
68118109 979507132
1
314757325 876264736
1
314757325 876264736
1
67889892 777031974
1
482602023 935398234
1
262404428 482602023
1
339427172 407785939
1
387917774 407785939
1
326338674 387917774
1
470606759 626121253
1
479458047 617726881
1
497240208 588812091
1
27983270 580400619
1...

output:

1058954050793
1702912646711
1725931854894
847704535346
735930701349
957982043978
689218108574
1014888485270
1253926159509
5082345003
326705049247
551722648510
670690834144
772997962207
64935508636
584174883094
608974709405
109201814393
118555421706
191964764942
1461647551481
1384656185989
3160951073...

result:

ok 300000 lines

Test #6:

score: 6
Accepted
time: 203ms
memory: 47144kb

input:

2000 1000000000
1
0 318307689
1
221844870 244163115
1
22662231 115199498
1
74219194 235801812
1
2902409 380433342
1
168375604 683138088
1
11701354 403914303
1
168632344 336967772
1
71867910 459961453
1
152644723 678746968
1
600952102 753759227
1
623175732 906107261
1
630957186 647533253
1
283639625 ...

output:

1501632404753
1875961436118
1998999999999
230648011712
554515884946
1810332112158
1414199310905
464373332232
756701388718
1232357794991
594169425622
207539360194
1483145438544
601736569489
71450010792
12219064269
262122526111
724970057025
409281412575
949114178961
415313478501
59936197914
1681006375...

result:

ok 300000 lines

Test #7:

score: 6
Accepted
time: 159ms
memory: 37108kb

input:

1384 702597566
1
91563503 395118179
1
272969378 336163563
1
93593482 288383752
1
641844047 657030228
1
24174550 474302755
1
483624997 516514674
1
223419444 649396752
1
277453784 660782113
1
217174776 378882844
1
315641289 693735319
1
251526833 482373541
1
381889032 694179867
1
103075862 361871540
1
...

output:

320794118590
115764966304
385279850930
10774072710
147778102717
240803564048
431539589908
290543953614
569466251816
22113396174
135588695866
228196386401
212848381901
88271083633
28719105225
481452322932
162201684606
579266864
322128177133
432606465712
97136428753
117887869786
563426915735
106522969...

result:

ok 235294 lines

Test #8:

score: 6
Accepted
time: 219ms
memory: 44508kb

input:

2000 1000000000
1
351194706 960606958
1
63449901 293827916
1
251243678 591560449
1
130608720 233558964
1
711982590 994358883
1
64238880 999558886
1
373830184 840719930
1
450224484 514836853
1
322667352 903701287
1
258721955 861235059
1
229925996 538977337
1
546018536 603533309
1
656999554 814169249
...

output:

917540572198
186307563686
364348161985
671810713222
368143529864
751354141909
398419559458
596576418307
19619304924
8364848267
507434978682
500879172382
200335632587
667972088008
955278113757
1106615668453
1200860863382
717853707983
277931060293
664485590193
152444963228
296133779011
563469393776
33...

result:

ok 300000 lines

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 8
Accepted
time: 170ms
memory: 35504kb

input:

401 1000000000
5
220371372 336231535
896142843 932588962
50422118 103225530
657147900 709375447
431588410 552424272
5
640842473 746383340
810978611 953826580
275021460 368433859
462990882 571587967
58700188 103678512
5
671571439 779339183
471320804 598246091
2249112 160803576
865566830 948052278
222...

output:

58015892805
52459605973
79838077191
17461955998
14664444928
41031111167
44824194366
23803651939
61071315346
12828269099
37025588232
22632816685
3687297996
23869715688
53256120071
26611104179
27660022154
43657337431
43421554887
33052332827
444354092
2245599618
3207243655
52828823244
29244408625
18672...

result:

ok 300000 lines

Test #10:

score: 8
Accepted
time: 163ms
memory: 34220kb

input:

401 1000000000
5
530204134 539929589
13144227 22318244
346386878 374628522
243477806 318307686
24550570 176767937
5
318307686 346386878
539929589 592275682
176767937 243477806
22318244 24550570
374628522 530204134
5
24550570 176767937
243477806 318307686
13144227 22318244
530204134 539929589
3463868...

output:

37011406343
19273967996
39579131455
169618941
18197860585
17273967996
13296451783
27169618941
3415507745
1333242651
26169618941
23517611345
8273967996
21517611345
1009174017
12526785362
27131150716
10333242651
20230333579
14056320836
22011406343
17296451783
3131150716
18011406343
20517611345
4352310...

result:

ok 300000 lines

Test #11:

score: 8
Accepted
time: 152ms
memory: 33548kb

input:

401 1000000000
4
848784509 854990717
82539068 388749940
876647585 917845619
434252359 592889838
5
917845619 963887179
388749940 434252359
854990717 876647585
592889838 848784509
79661360 82539068
4
434252359 592889838
876647585 917845619
82539068 388749940
848784509 854990717
5
79661360 82539068
854...

output:

39069061110
33115102670
49881348111
37483593260
28483593260
20529095679
9838184259
28108896462
16575137239
27529095679
6838184259
40027863076
11108896462
30062854902
23881348111
15370997341
27069061110
11529634820
13370997341
4069061110
38115102670
28575137239
16006206208
324955781
10529095679
23115...

result:

ok 300000 lines

Test #12:

score: 8
Accepted
time: 152ms
memory: 34664kb

input:

401 1000000000
4
494963273 820408129
83880819 120938110
842771080 916665396
126044810 290806569
5
64152734 83880819
820408129 842771080
290806569 494963273
120938110 126044810
916665396 991266558
4
126044810 290806569
83880819 120938110
842771080 916665396
494963273 820408129
5
820408129 842771080
6...

output:

44795843296
23631081537
49907385739
29907385739
32283273730
2448035489
23056785376
14674555144
35056785376
3206925750
22206925750
11674555144
6448035489
13470398440
2061892076
13448035489
26061892076
674555144
1037057291
19907385739
5206925750
8631081537
2283273730
631081537
15470398440
42795843296
...

result:

ok 300000 lines

Test #13:

score: 8
Accepted
time: 174ms
memory: 37352kb

input:

601 1000000000
1
1875338 891632702
5
25665841 55060068
659511452 708955140
481273243 580847341
711209775 812323888
232189221 411128242
1
1875338 891632702
5
481273243 580847341
711209775 812323888
25665841 55060068
659511452 708955140
232189221 411128242
1
1875338 891632702
5
232189221 411128242
711...

output:

132889757364
545053184730
599053184730
349053184730
367180422927
378889757364
181053184730
214889757364
25053184730
119343850293
51180422927
165180422927
293180422927
367180422927
569343850293
449343850293
445053184730
115180422927
341053184730
218889757364
189053184730
107180422927
105343850293
272...

result:

ok 300000 lines

Test #14:

score: 8
Accepted
time: 43ms
memory: 10292kb

input:

2 1000000000
5
562116384 862271817
248809078 388152605
82837362 988267899
133736084 529736108
468265107 868556204
300000
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:

139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
...

result:

ok 300000 lines

Test #15:

score: 8
Accepted
time: 197ms
memory: 46052kb

input:

1343 1000000000
1
96816138 421462953
1
69729216 475015093
1
283255283 678004962
1
278183246 599578883
1
286424703 774388986
1
406934648 652124894
2
248195189 472085327
391961014 813907536
1
501741026 753654366
2
245060443 436672588
574556343 749900723
2
68441219 101302096
259996265 760303051
1
72484...

output:

413507395543
186533587467
765911134712
208868482018
750404829806
371009807668
207418964932
82428131468
227003029730
376762196348
758844081281
297910927314
116614837962
284886215974
115872729613
739953553340
22687331071
38063290673
8397417592
12376556003
111406561501
687952964749
12358874327
12241911...

result:

ok 300000 lines

Test #16:

score: 8
Accepted
time: 168ms
memory: 40880kb

input:

688 1000000000
3
53194187 264960020
92885755 475277088
211238915 509880505
3
6401156 232019227
469999920 577170462
554975681 644492768
2
60786527 521736047
379366223 840946783
5
419561 60298271
65502307 288235251
144008397 577008215
394990239 683091070
590837826 726885528
5
34176214 267349290
223828...

output:

68635449756
17399644966
829516162
145106947024
213624911279
172079871542
83795296584
86980633523
92389124653
242968110321
130973680158
126653516847
55386113669
195171481102
213220346364
18461195442
46294965858
108144706452
39788445054
253134167975
234247708477
234680737798
241401743091
222796922152
...

result:

ok 300000 lines

Test #17:

score: 8
Accepted
time: 211ms
memory: 47924kb

input:

1343 1000000000
1
109453710 560177810
1
661213206 913808522
1
96816138 421462953
1
193580993 240625496
1
418456250 930846898
1
69729216 475015093
2
36690281 582664217
176453344 242348112
1
283255283 678004962
2
62188679 608199380
90371766 461894091
2
278183246 599578883
255503843 861802590
1
5501148...

output:

755163082049
346535864122
512232407863
978898058885
290552425232
97892014092
196290407373
506354231170
334498014469
284757164242
115371682131
62648300672
346925420676
384891531485
477119667452
63592230021
727135372228
847646760248
640469173746
892644815785
815536555442
725960919828
92996821933
41864...

result:

ok 300000 lines

Test #18:

score: 8
Accepted
time: 187ms
memory: 41472kb

input:

688 1000000000
3
423977827 524383260
470022669 702490366
226130327 278353378
3
297592874 610688336
79889464 986165439
132108640 133164848
2
92885755 509880505
53194187 211238915
5
264960020 475277088
262659468 993117970
127768091 586472847
838692371 844797839
414832478 764033423
5
132569548 29971860...

output:

326730918498
121718776974
78578695164
28500146125
259901663572
262316540686
278578980688
83091064134
24828685743
280173281064
305172418316
69583809374
329513749863
295544205317
40964341057
32266429473
20655624467
142566212889
70252960623
218573155987
10170931375
250505042674
221374816018
41528906065...

result:

ok 300000 lines

Subtask #3:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #19:

score: 17
Accepted
time: 513ms
memory: 766176kb

input:

78947 750547470
1
163829932 170313421
1
34754818 519560348
1
93869768 456876196
1
202438570 204178463
1
98944286 525531897
1
179303298 240997860
1
134306886 372058731
1
187793519 715404428
1
126696643 473999960
1
394050514 679516860
1
286238164 460635018
1
489600305 744982147
1
157363526 311748138
1...

output:

6205466879608
20259844164215
41141586068816
37267587927279
39826818642517
4093515572405
43823341232727
17711628858751
28238993418477
40884190272133
26104208475807
13508775709102
41012054001186
35352426273830
461627182416
19671175078208
21652186528249
28225447363916
41145479364020
41071413078809
3081...

result:

ok 206901 lines

Test #20:

score: 0
Runtime Error

input:

100000 1000000000
1
499402020 514605324
1
766295491 995958303
1
96603365 780877499
1
712910081 985226165
1
454949900 743899539
1
21691952 722721408
1
211340490 405034439
1
85107353 123109353
1
706000294 838706369
1
38501709 366714034
1
197050586 597553366
1
394077551 422415760
1
722716322 890440304
...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%

Subtask #5:

score: 0
Time Limit Exceeded

Test #39:

score: 36
Accepted
time: 233ms
memory: 858684kb

input:

301 1000000000
300
863578477 865166395
261293731 262628986
290161866 292035987
31029640 32135494
288138979 289416854
321254857 322352244
163393949 166291828
897880953 899050317
840019366 842900569
100947276 102350870
520716771 522094941
820182602 822928836
766708508 769688128
727827782 728874133
740...

output:

996840913
213467673
996840913
350088722
393643222
660161043
23398481
83378757
386772057
550058707
116797789
66795163
230046137
430022213
50052816
646976316
223372288
443414533
153481147
43516132
10186037
656745708
93473524
443593864
613442576
306857640
606706973
613462088
456791451
276831487
1034634...

result:

ok 90000 lines

Test #40:

score: 36
Accepted
time: 263ms
memory: 858496kb

input:

301 1000000000
300
300066064 302323286
473632893 475766284
351370863 352221960
914819860 916333465
317977421 319127906
920520037 923283324
504830796 505586396
494369607 495452979
558040391 558539388
23365739 25905186
564630891 565459633
277441881 279789082
961207919 962159794
693338597 695347090
578...

output:

286865169
313364540
996793841
720065430
783551270
320062652
50110451
340091416
456818265
106730063
250074295
56771021
100124212
90126317
70034915
413435450
426731145
213397678
46770743
113477622
30125146
266748001
793374963
343416973
130072106
880090066
26828815
196784156
596947893
460085415
6752386...

result:

ok 90000 lines

Test #41:

score: 36
Accepted
time: 214ms
memory: 861392kb

input:

301 1000000000
300
436133849 439766906
399299656 399871397
987510123 987623863
87382570 87807552
948515445 949052052
596367083 597547004
838965514 843316163
505192505 507242632
813023000 816438712
680226676 681650508
241702689 242610357
903574024 904180573
293115387 293225805
965934333 967856315
359...

output:

375138342
196630758
480427492
72200479
226103302
192548720
405758667
18014460
276454760
287183968
7303408
148051928
324101075
70716872
167805126
79418501
87154832
328873671
90156751
401532551
18997429
2458843
110069678
86903655
870988
34835290
196364999
201922538
108740749
235174223
181778722
869036...

result:

ok 90000 lines

Test #42:

score: 36
Accepted
time: 211ms
memory: 858420kb

input:

301 1000000000
299
770778382 771390993
731130505 734282136
900324353 900756667
315720590 315879945
549885731 551694156
961870218 967237404
449686711 450724459
169164766 176907126
418234610 418840696
874086997 874800159
746489809 746815743
704004512 705083659
779639958 782291940
538072804 539490105
9...

output:

278151674
48664023
474375584
192834
89456431
315809268
464386665
92387184
365717998
311285027
11591638
42204183
161647182
166728915
160331861
116815686
458008311
11591638
185637145
210866239
134761268
3137894
49495155
157947203
6416710
216770354
112128268
54180198
20566729
15835368
202054033
4204761...

result:

ok 90000 lines

Test #43:

score: 36
Accepted
time: 257ms
memory: 858820kb

input:

301 1000000000
299
333948864 338012623
912826899 913391055
571148299 577968736
372988318 373399550
162424522 165729804
754997109 756545766
55958658 57190515
677609768 681027389
834938974 837016269
366716733 367166710
176358492 176855515
146676373 152623195
967011409 969970853
302962786 308603483
421...

output:

215116970
309596332
449007971
86708426
89020740
1378772
164417408
123121994
258650249
31734252
208339511
329295444
226562183
56266419
265427201
26290202
182058675
11508341
18364019
216120098
16779760
224579848
3856163
40562766
124790659
266181589
141282804
20226095
347296033
264493325
34033836
32337...

result:

ok 90000 lines

Test #44:

score: 36
Accepted
time: 241ms
memory: 858688kb

input:

301 1000000000
300
614330645 904777865
21671200 972465607
844511005 869900059
222039406 973766970
50412921 890784128
448643606 930527499
321278854 633891369
339898318 978093316
494050725 535513007
681208047 744770267
86200056 932879083
882937423 926179572
142953625 486908718
433164812 480712775
5911...

output:

10347846948
11800848772
17261653888
98905
10314234020
2957329058
4417151526
3039339968
7285236230
6570977671
6331232853
14679251466
8707228611
300284111
4990743980
7676381144
8350448209
7885156273
6425522914
4190367169
8020285333
14717882755
160647082
438592292
2582876959
4586484
9574940726
43663620...

result:

ok 90000 lines

Test #45:

score: 36
Accepted
time: 182ms
memory: 858548kb

input:

301 1000000000
1
1334350 998890869
599
971308804 975093823
759737391 761610435
787176304 787284902
816238240 816573264
858109281 860240492
920044373 921239817
343319757 345239835
346094920 346102391
736650483 736783277
577150165 577890956
184122044 185187782
314131298 314627686
204408708 204445102
6...

output:

235000647581
87000647581
299000647581
170997556519
27000647581
121001538193
111004629255
60997556519
73004629255
23004629255
127004629255
109000647581
43001538193
81001538193
79004629255
177000647581
73004629255
188997556519
25000647581
55001538193
17004629255
183000647581
103000647581
119000647581
...

result:

ok 90000 lines

Test #46:

score: 36
Accepted
time: 32ms
memory: 855588kb

input:

2 1000000000
90000
124621107 763212064
251817510 936472509
993219630 994601989
137121582 138175347
278276318 575480374
490851352 496516863
654522838 977035777
223624214 774171212
452916446 457640243
982885774 984407786
80264328 886909856
20220167 476582796
923495569 927815157
95304908 96679851
15446...

output:

43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
...

result:

ok 90000 lines

Test #47:

score: 36
Accepted
time: 521ms
memory: 859980kb

input:

90000 1000000000
1
338316860 644977262
1
563229885 715913633
1
335134604 752347690
1
625869440 822316033
1
795020960 990410399
1
281092649 637534374
1
401749186 605375797
1
364028027 560879591
1
437100466 932728915
1
47282941 348181727
1
146320889 885304930
1
5931022 880672331
1
372980219 595366588
...

output:

53768648355483
23838206213541
54639890432191
54626071351229
54620783971213
54633457136337
53796086503560
53371216359653
47171932914429
47690622286737
12779024553400
14291140362267
54621717013982
53564336324001
34113438470190
14257801391203
54500354471647
52911934965281
46702212341124
28109074944513
...

result:

ok 90000 lines

Test #48:

score: 36
Accepted
time: 343ms
memory: 861656kb

input:

60079 1000000000
1
253782450 453522147
1
168581347 819446881
1
451623493 804648849
1
96689328 297947513
1
568567663 753006192
1
136248021 352134084
2
213716273 281499582
340303924 345505579
1
693448835 875475762
2
82796452 571095152
591684256 596522691
2
174711924 834329131
509836504 897647103
2
588...

output:

23748161791455
23808223741525
32703390861713
23671406800914
22277497154338
6528635850090
22309408468539
23045471979897
23766008116235
18678652901918
12146667312943
23700943591244
396327395474
23809301713385
38255070436059
20542266534480
1650256157524
20434443955493
29627140458924
3801589804354
21528...

result:

ok 90000 lines

Test #49:

score: 36
Accepted
time: 230ms
memory: 862208kb

input:

30059 1000000000
2
462069213 497789433
718311044 777370852
2
166968492 337050767
682764763 703100408
1
170223771 361271214
1
12437094 156663631
5
88712882 466784605
185303511 573910587
280556990 858685481
437877878 868470162
723102405 871554647
4
153331570 305826348
214959971 636146568
344643556 791...

output:

8819134597055
15467174865861
8807727903392
13167271964440
13246196492496
8432704137443
15473630461645
8808523951430
6478360832294
15410061508146
6159478112442
8832460910193
263765343200
5496440428082
3038791544438
11688312354684
8815867919342
7715984235574
8443541510153
7834972972137
10885661641327
...

result:

ok 90000 lines

Test #50:

score: 36
Accepted
time: 171ms
memory: 859532kb

input:

19004 1000000000
4
17206998 281766058
84488752 282994887
627425516 748672588
951308237 982130356
5
87890233 339680056
245855594 356952771
359686187 652998154
426238017 663778482
880913537 907711864
2
115260936 207032110
718881449 739560320
3
41956730 471715219
335629962 736275482
864030335 999290375...

output:

1099534056627
1991434504019
847269201976
528051945483
1659766599758
4374456430605
5022451902450
3742732803311
5944843968278
459717145972
1483415528185
3959600286689
5049192052556
873200004808
923403984856
1183434650393
4356588642462
2429113619294
627069567181
3937135819996
2841700935705
539008261647...

result:

ok 90000 lines

Test #51:

score: 36
Accepted
time: 188ms
memory: 859096kb

input:

18916 1000000000
4
346783099 470848200
559020259 602178066
577282980 661843175
680381683 823131053
4
47066782 148949315
252043225 637023874
401154833 671819033
784111616 989739428
3
8865129 502866987
265992679 807208282
335662478 930136515
4
200458018 317869777
299741514 395799404
370552553 42806770...

output:

3238729533437
777639478693
4391830958910
3352206627657
560413368584
3198338814211
971643878797
4464331123228
1356419370120
162750212568
2277431305786
1466513600403
2065619963790
5475585276731
456350584073
164290582872
1833082463519
5836737218669
1487059271239
2605671594492
2904728024118
270474999315...

result:

ok 90000 lines

Test #52:

score: 36
Accepted
time: 190ms
memory: 861832kb

input:

19276 1000000000
2
325514438 836447215
366949679 998648867
5
176147835 552851139
310657024 583334999
339031648 628759843
383618367 745869472
529066413 760323693
5
167007348 353080479
242762963 770910232
343271308 780138092
761154681 921974020
801679864 981937499
2
677641365 758709349
717559356 91317...

output:

6146626238735
5208726718183
4873849912054
938118247453
1286346562828
7432689413610
6494789893058
3271206192187
5962875763505
2875597358157
1937697837605
4557269367062
7671382629633
4795133220518
1525110132395
2462874638351
252144514610
8957445804508
1554320142865
3118850461637
4400353749055
35692884...

result:

ok 90000 lines

Test #53:

score: 36
Accepted
time: 163ms
memory: 861628kb

input:

18917 1000000000
4
29027499 231827499
75725779 470160321
757586713 886276634
839636169 955825903
4
25198161 123103176
128378821 281135131
292543311 728917163
831388778 932162077
2
170528494 174338978
447917091 918975216
5
67218787 110234236
524805314 529179462
565957537 794120654
676108363 928751425...

output:

8804900918200
2665479789262
5286329772885
8751033634475
1662657739
4470338018288
6411041892914
3022197488802
1803791271441
8818607269492
4471929186164
7545095018845
7546686186721
3075153377575
5566332577410
8822920352638
1687286902175
6406569732507
1210727151777
6408160900383
4642359006499
452270264...

result:

ok 90000 lines

Test #54:

score: 36
Accepted
time: 118ms
memory: 858896kb

input:

1349 1000000000
70
710840 12547216
12027935 14765000
45359588 56936295
54803263 117798657
62417340 127445061
79707220 155214313
116425661 157330890
123815671 163519836
127280759 169532931
128017177 169810531
157717367 176729720
175805039 191910573
180077045 214840008
190718287 253202862
194576606 25...

output:

10781653274
27537649262
48834402099
59936019762
23633004844
96602064710
75397807064
63999979984
62628635690
23755098026
20851554912
48087001866
56779694182
33221044656
55263078069
85944602073
19804272313
46717549969
79115920469
2172263661
163176343821
2181981715
38223322141
60040522674
16220655154
1...

result:

ok 90000 lines

Test #55:

score: 36
Accepted
time: 135ms
memory: 855872kb

input:

439 1000000000
131
7221855 26021118
11247662 27485090
13203383 43732905
19025877 60681483
31692809 66177446
57349733 78795904
60479885 87280104
65785454 102219068
68074326 104132708
84499701 104637224
86923670 114703218
88211666 115613399
89152491 124985965
91240046 125114975
92740268 126318040
1155...

output:

6987434367
15121381263
16016359740
6281405495
8180280367
14829169475
17044385632
16715485074
16046486922
13762775361
16709338979
17011264378
16922403923
20851435677
11187658535
15876670419
12309881163
14996141181
17282654034
11670577356
770601012
11290351428
17088373268
17470030210
13853389363
15874...

result:

ok 90000 lines

Test #56:

score: 36
Accepted
time: 378ms
memory: 860732kb

input:

65537 1000000000
123
15647797 26276884
24099356 26562597
25173015 35877256
25309676 35908612
25500436 40902791
26773458 49162342
28202078 60954901
28661059 75097034
39620318 84893746
40033859 89497884
41156937 99087857
44863583 112043683
45485113 136718814
47298165 139470597
73487680 179698537
77689...

output:

53611763750012
53611854446856
53608068353087
53610588088006
53609927617148
53609586268573
53609092687920
53612928948899
53613495033275
53611534068783
53613381067324
53607688772019
53613036369520
53610933955292
53608235078322
53608374640242
53608172527281
53607839953422
53612437672948
53608267316791
...

result:

ok 90000 lines

Test #57:

score: 36
Accepted
time: 383ms
memory: 858464kb

input:

65537 1000000000
122
1889078 25485586
11496455 42226678
22157707 49942564
28705187 54233818
30882333 57815041
34164017 66711429
36461936 72957299
51572963 73766466
55442614 74375514
56159030 89108667
61922084 94310000
68898461 112505745
72158317 144525759
79971387 149956563
81661858 153588290
822228...

output:

53637869918578
53639529230666
53641372757881
31141835439154
53638962084558
4738168997864
137879367
53641331054033
20976273887557
53642221046565
53643541777071
15294532151916
53640869184451
10748034134999
53643602621432
16254822803639
53639425323000
53640689714818
53637258583177
53638798658004
536357...

result:

ok 90000 lines

Test #58:

score: 36
Accepted
time: 230ms
memory: 856888kb

input:

32769 1000000000
203
5326613 6989434
11240161 14377000
13779338 22139081
15434449 23950904
17231890 31940393
27207939 51941996
32191753 52497542
33159596 58019894
42580464 62597952
44850480 62757913
45230030 63174191
46198116 69160794
51561702 72935802
51770120 75405691
55984600 81379904
59192416 83...

output:

25183360671664
25181881858229
25183922607430
25185847299285
25189780214763
25183054492530
25182993360633
25183916325357
25185601986093
25187260040621
25185187239360
25181910622090
25179597969445
25185901430414
25183056907042
25178957292291
25181419475036
25181545734302
25187943555472
25184475146938
...

result:

ok 90000 lines

Test #59:

score: 36
Accepted
time: 267ms
memory: 857532kb

input:

32769 1000000000
159
4043997 15813032
4653260 25706651
5918786 28045943
10032013 32672981
11735141 34624749
25060207 51490131
32417268 54929219
41516083 62429592
51911462 63030137
52654757 67285847
54621196 81839076
74937166 87933709
87836792 91197205
93455387 99682377
94609411 118012230
98599431 11...

output:

9565014061666
25189477100784
25192613131873
25190871788482
25194594158839
8483067490973
25192513226030
25198986522164
25195810219523
25195580099338
25191552686502
25194190712539
3633836239554
12408525239823
25197834538904
25194267561137
25196813205003
25199541197450
25197823984120
25191734178796
251...

result:

ok 90000 lines

Test #60:

score: 0
Time Limit Exceeded

input:

32769 1000000000
22508
7941 36860
11840 49693
32536 78269
33129 230244
55388 234880
71100 328210
216923 350020
270665 374416
333542 442531
401937 543459
431040 597063
453889 616546
466363 648376
486519 662874
505371 687189
540441 722006
546471 757356
548604 759419
718271 799734
764022 867368
789652 ...

output:

16245344572138
3845268927323
2344505645168
23069299954893
976651238900
13873747933176
15383144051876
15485518342846
5011473862202
12503706960624
22895565348851
13803877202931
10843522908064
7331309730304
14253686149422
14534465150101
2500589096229
7499478224060
18434865906175
13307864129258
19101343...

result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%