QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624322 | #8649. Escape Route 2 | hhoppitree | 0 | 663ms | 859340kb | C++17 | 2.7kb | 2024-10-09 15:32:44 | 2024-10-09 15:32:44 |
Judging History
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%