QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#439992 | #8649. Escape Route 2 | nhuang685 | 23 | 441ms | 115436kb | C++20 | 3.6kb | 2024-06-12 22:23:07 | 2024-06-12 22:23:08 |
Judging History
answer
/**
* @file qoj8649-2.cpp
* @author n685
* @brief
* @date 2024-06-11
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
const int64_t LLINF = static_cast<int64_t>(4e18);
const int LG = 18;
auto solve(int n, int64_t t, std::vector<int> m,
std::vector<std::vector<std::pair<int64_t, int64_t>>> f, int q,
std::vector<std::pair<int, int>> qq) -> std::vector<int64_t> {
for (int i = 0; i < n - 1; ++i) {
std::sort(f[i].begin(), f[i].end());
int64_t mi = LLINF;
for (int j = m[i] - 1; j >= 0; --j) {
mi = std::min(mi, f[i][j].second);
f[i][j].second = mi;
}
}
std::vector lift(LG, std::vector<std::vector<int64_t>>(n - 1));
for (int i = 0; i < n - 1; ++i) {
lift[0][i].resize(m[i] + 1);
for (int j = 0; j < m[i]; ++j) {
lift[0][i][j] = f[i][j].second;
}
lift[0][i][m[i]] = t + f[i][0].second;
}
for (int i = 1; i < LG; ++i) {
for (int j = 0; j < n - 1 && j + (1 << i) < n; ++j) {
lift[i][j].resize(m[j] + 1);
for (int k = 0; k <= m[j]; ++k) {
int64_t time = lift[i - 1][j][k];
int mid = j + (1 << i >> 1);
int ind = static_cast<int>(
std::lower_bound(f[mid].begin(), f[mid].end(),
std::pair{time % t, static_cast<int64_t>(0)}) -
f[mid].begin());
lift[i][j][k] = t * (time / t) + lift[i - 1][mid][ind];
}
}
}
auto query = [&](int l, int r, int ind) -> int64_t {
int64_t dist = r - l;
int64_t st = f[l][ind].first;
int64_t time = f[l][ind].first;
for (int i = LG - 1; i >= 0; --i) {
if (((1 << i) & dist) == 0) {
continue;
}
if (st != time) {
ind = static_cast<int>(
std::lower_bound(f[l].begin(), f[l].end(),
std::pair{time % t, static_cast<int64_t>(0)}) -
f[l].begin());
}
time = t * (time / t) + lift[i][l][ind];
int nxt = l + (1 << i);
l = nxt;
}
return time - st;
};
std::vector<int64_t> ans(q, LLINF);
for (int j = 0; j < q; ++j) {
auto [l, r] = qq[j];
if (m[l] > m[r] && l != 0 && r != n - 1) {
continue;
}
for (int i = 0; i < m[l]; ++i) {
ans[j] = std::min(ans[j], query(l, r, i));
}
}
return ans;
}
auto main() -> int {
#ifndef LOCAL
std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
int n;
int64_t t;
std::cin >> n >> t;
std::vector<int> m(n);
std::vector<std::vector<std::pair<int64_t, int64_t>>> f(n - 1);
for (int i = 0; i < n - 1; ++i) {
std::cin >> m[i];
f[i].resize(m[i]);
for (auto &[a, b] : f[i]) {
std::cin >> a >> b;
}
}
int q;
std::cin >> q;
std::vector<std::pair<int, int>> qq(q);
for (int i = 0; i < q; ++i) {
std::cin >> qq[i].first >> qq[i].second;
--qq[i].first;
--qq[i].second;
}
std::vector<int64_t> a1 = solve(n, t, m, f, q, qq);
m.pop_back();
std::reverse(m.begin(), m.end());
std::reverse(f.begin(), f.end());
for (int i = 0; i < n - 1; ++i) {
for (auto &[a, b] : f[i]) {
a = (t - 1) - a;
b = (t - 1) - b;
std::swap(a, b);
}
}
m.push_back(0);
for (auto &[l, r] : qq) {
l = (n - 1) - l;
r = (n - 1) - r;
std::swap(l, r);
}
std::vector<int64_t> a2 = solve(n, t, m, f, q, qq);
for (int i = 0; i < q; ++i) {
std::cout << std::min(a1[i], a2[i]) << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 37ms
memory: 12448kb
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: 0
Accepted
time: 71ms
memory: 11788kb
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
Accepted
time: 91ms
memory: 14052kb
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: 0
Accepted
time: 69ms
memory: 12036kb
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: 0
Accepted
time: 90ms
memory: 14148kb
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: 0
Accepted
time: 82ms
memory: 14276kb
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: 0
Accepted
time: 63ms
memory: 11716kb
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: 0
Accepted
time: 92ms
memory: 14072kb
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: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #9:
score: 8
Accepted
time: 254ms
memory: 12884kb
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: 0
Accepted
time: 255ms
memory: 13044kb
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
Wrong Answer
time: 159ms
memory: 12884kb
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 4000000000000000000 4000000000000000000 27529095679 6838184259 40027863076 4000000000000000000 30062854902 23881348111 4000000000000000000 27069061110 11529634820 4000000000000000000 4069061110 38115102670 40000000000...
result:
wrong answer 8th lines differ - expected: '28108896462', found: '4000000000000000000'
Subtask #3:
score: 17
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 17
Accepted
time: 291ms
memory: 89992kb
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
Accepted
time: 441ms
memory: 115364kb
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:
51002827556551 51058928322620 54456195364152 33985756298880 40843294364814 15102513736222 54474740890294 38132310544449 45962379244811 81828173456918 45953634597664 54383361960561 81724265807653 54486863608036 7943440845221 52922599405365 54528389564372 54359675413858 54480599618780 55927751535912 1...
result:
ok 300000 lines
Test #21:
score: 0
Accepted
time: 437ms
memory: 115284kb
input:
100000 1000000000 1 172079429 475324295 1 400518916 720769657 1 274370833 437066961 1 69640537 354880456 1 105708389 515119134 1 460245448 491168511 1 305736062 908867012 1 409879705 700345897 1 807448587 900734950 1 21167124 802349010 1 29646241 451672345 1 401101164 849231397 1 143742860 355220627...
output:
3322786217605 54519197542433 51507236182424 51038288475992 54515310283834 54451772579395 40445305754310 12499014691181 64287958279392 5165502765728 54536981294065 33993047573307 50203125083627 4287962267265 32543278978791 29553771479908 6634090289361 24497834416407 54510411009409 54478989372687 5448...
result:
ok 300000 lines
Test #22:
score: 0
Accepted
time: 358ms
memory: 113084kb
input:
100000 848784505 1 27033502 308637216 1 1438562 377905811 1 377905811 445448307 1 377905811 445448307 1 160564479 367847022 1 29086295 441763868 1 10492385 29086295 1 29086295 730214588 1 272693597 730214588 1 8185380 43275068 1 6374476 782898366 1 4005270 6374476 1 3501828 5751498 1 890858 5072034 ...
output:
40155094458849 53957285623801 74314870396875 39710068492963 247825537284 9491774378246 1792570550982 11487043081182 39927445813086 7518209178048 1868430585731 9399975086886 42289338923347 7444371932154 16049020333361 46632817179506 40333365472902 22933944313580 38418501333554 23288694741242 47056670...
result:
ok 226053 lines
Test #23:
score: 0
Accepted
time: 415ms
memory: 115436kb
input:
100000 1000000000 1 83880822 730819402 1 35594124 752445375 1 18704793 668403352 1 17474165 931488188 1 15086956 950700936 1 35712962 969944984 1 969944984 988879345 1 978906485 997699198 1 988078833 989460959 1 333539740 989236085 1 992834981 993928865 1 993836625 993928865 1 993877892 993928865 1 ...
output:
50616175045053 69001077953362 87602914201257 9400991126552 13076249428282 3302796985315 20277989521385 22218930829541 30336682428616 49125555454337 31148275992440 17955973903932 28958997325743 47631793498371 42949340374080 15065991559529 48988320931729 42577974657383 21914787769912 54987999529326 82...
result:
ok 300000 lines
Test #24:
score: 0
Accepted
time: 406ms
memory: 115268kb
input:
100000 1000000000 1 0 55060072 1 3570003 718349783 1 256078893 403790490 1 389580948 656859885 1 610267686 893795343 1 659511452 663711653 1 1875338 798640433 1 761217675 830966093 1 325102503 422332552 1 52703351 777206866 1 632813519 799618334 1 591942509 965790256 1 943567255 992355350 1 81550764...
output:
59312736241277 82196943632763 99998999999999 23986078307126 2509122248637 42012837406787 28611768219019 65210377806133 556560473013 15606679568159 5810556495394 46933725843182 71288948739119 11091807824559 90582129788769 23140905870202 17705197665416 25352553201248 38685906120426 55367891999341 9724...
result:
ok 300000 lines
Test #25:
score: 0
Accepted
time: 287ms
memory: 90024kb
input:
78947 750547470 1 12801326 300178508 1 163829932 629108909 1 170313421 475428191 1 419182442 552951314 1 34754818 519560348 1 3594075 419329694 1 456876196 654341696 1 29308134 93869768 1 83056966 497182026 1 204178463 450250065 1 202438570 465078541 1 55014422 368356153 1 98944286 386133586 1 52553...
output:
33684588782336 10599029692975 46269013081090 38276748912791 37664428117700 3243264461448 16441523547215 15541405847231 19207973709712 10394890624052 183262146076 14345085397720 28902769238369 3218092520743 33009007885846 10621151273560 29740815235729 48877373310335 36045937597311 10838456331639 2082...
result:
ok 206901 lines
Test #26:
score: 0
Accepted
time: 424ms
memory: 115436kb
input:
100000 1000000000 1 395765 716053221 1 208668935 499402020 1 514605324 573424149 1 112563488 430804151 1 766295491 995958303 1 370896512 442618404 1 155109978 225449821 1 96603365 780877499 1 305211230 986836650 1 322663385 970957503 1 712910081 985226165 1 297230409 621959309 1 208656221 743899539 ...
output:
30662391785500 57766779240503 6111126043334 42002498505076 19753415630398 16369656055632 3834523157128 4728497583038 9546264570412 67330624722110 25516282773156 32679967205145 41165867776209 35357315307254 49979790494981 49838551462323 20813782279079 45227041005079 6586079790185 75982320601677 16933...
result:
ok 300000 lines
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Time Limit Exceeded
Test #39:
score: 0
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%