QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624322#8649. Escape Route 2hhoppitree0 663ms859340kbC++172.7kb2024-10-09 15:32:442024-10-09 15:32:44

Judging History

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

  • [2024-10-09 15:32:44]
  • 评测
  • 测评结果:0
  • 用时:663ms
  • 内存:859340kb
  • [2024-10-09 15:32:44]
  • 提交

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; ++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], now = Nxt[now][step % sz];
            S += BIGVNxt[now][step / sz], now = BIGNxt[now][step / sz];
            res = min(res, S);
        }
        printf("%lld\n", M[{l, r}] = res);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 180ms
memory: 36904kb

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: 0
Wrong Answer
time: 201ms
memory: 49760kb

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:

wrong answer 4722nd lines differ - expected: '1642055523719', found: '4552925040'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #39:

score: 36
Accepted
time: 387ms
memory: 855820kb

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: 357ms
memory: 854872kb

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: 322ms
memory: 855788kb

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: 331ms
memory: 853304kb

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: 341ms
memory: 854448kb

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: 291ms
memory: 854868kb

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: 248ms
memory: 856116kb

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: 43ms
memory: 852384kb

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: 663ms
memory: 859340kb

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: 511ms
memory: 858156kb

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: 291ms
memory: 858032kb

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: 212ms
memory: 855528kb

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: 203ms
memory: 856440kb

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: 0
Wrong Answer
time: 216ms
memory: 858828kb

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:

wrong answer 16575th lines differ - expected: '10194270042397', found: '441267278'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%