QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520954 | #8649. Escape Route 2 | green_gold_dog# | 0 | 533ms | 28468kb | C++20 | 4.4kb | 2024-08-15 18:10:10 | 2024-08-15 18:10:11 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr long long INF64 = 9'000'000'000'000'000'000;
constexpr ll INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 17;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
struct LA {
vector<vector<ll>> arr, ends, lbnxt;
vector<vector<vector<ll>>> smk;
vector<vector<vector<pair<ll, ll>>>> binup;
map<pair<ll, ll>, ll> mind;
LA(vector<vector<pair<ll, ll>>> a, ll dt) {
ll n = a.size();
arr.resize(n);
ends.resize(n);
for (ll i = 0; i < n; i++) {
sort(a[i].begin(), a[i].end());
ll bto = INF32;
while (!a[i].empty()) {
if (a[i].back().second < bto) {
bto = a[i].back().second;
arr[i].push_back(a[i].back().first);
ends[i].push_back(a[i].back().second);
}
a[i].pop_back();
}
reverse(arr[i].begin(), arr[i].end());
reverse(ends[i].begin(), ends[i].end());
}
lbnxt.resize(n);
for (ll i = 1; i < n; i++) {
lbnxt[i].resize(ends[i - 1].size());
for (ll j = 0; j < ends[i - 1].size(); j++) {
lbnxt[i][j] = lower_bound(arr[i].begin(), arr[i].end(), ends[i - 1][j]) - arr[i].begin();
}
}
binup.resize(n);
for (ll i = n - 1; i >= 0; i--) {
binup[i].resize(arr[i].size());
for (ll j = 0; j < arr[i].size(); j++) {
binup[i][j].resize(LOG);
binup[i][j][0] = make_pair(0, j);
for (ll k = 1; k < LOG; k++) {
pair<ll, ll> ans = binup[i][j][k - 1];
ll nextv = i + (1 << (k - 1));
if (nextv >= n) {
break;
}
ll num = lbnxt[nextv][ans.second];
if (num == arr[nextv].size()) {
num = 0;
ans.first++;
ans.second = 0;
}
binup[i][j][k] = make_pair(ans.first + binup[nextv][num][k - 1].first, binup[nextv][num][k - 1].second);
}
}
}
smk.resize(n);
for (ll i = 0; i < n; i++) {
vector<ll> all;
for (ll j = 0; j < arr[i].size(); j++) {
all.push_back(j);
}
for (ll sz = 0; sz < LOG; sz++) {
if (i + (1 << sz) > n) {
break;
}
smk[i].push_back(vector<ll>(0, 0));
long long lst = INF64;
while (!all.empty()) {
long long x = get(i, 1 << sz, all.back(), dt);
if (x != lst) {
smk[i].back().push_back(all.back());
lst = x;
}
all.pop_back();
}
reverse(smk[i].back().begin(), smk[i].back().end());
all = smk[i].back();
}
}
}
long long get(ll v, ll x, ll st, ll dt) {
ll d = 0, t = st;
bool b = true;
for (ll i = LOG - 1; i >= 0; i--) {
if ((x >> i) & 1) {
x ^= 1 << i;
ll num;
if (b) {
b = false;
num = t;
} else {
num = lbnxt[v][t];
}
if (num == arr[v].size()) {
num = 0;
d++;
t = 0;
}
d += binup[v][num][i].first;
t = binup[v][num][i].second;
v += 1 << i;
}
}
return dt * (long long)d + ends[v - 1][t];
}
long long get(ll v, ll x, ll dt) {
if (mind.find(make_pair(v, x)) != mind.end()) {
return mind[make_pair(v, x)];
}
ll p2 = 0;
ll nx = x;
while (nx > 1) {
nx /= 2;
p2++;
}
long long ans = INF64;
for (auto i : smk[v][p2]) {
assign_min(ans, get(v, x, i, dt) - arr[v][i]);
}
return mind[make_pair(v, x)] = ans;
}
};
void solve() {
ll n, t;
cin >> n >> t;
vector<vector<pair<ll, ll>>> to(n - 1);
for (ll i = 0; i < n - 1; i++) {
ll col;
cin >> col;
for (ll j = 0; j < col; j++) {
ll a, b;
cin >> a >> b;
to[i].emplace_back(a, b);
}
}
LA la(to, t);
ll q;
cin >> q;
for (ll i = 0; i < q; i++) {
ll l, r;
cin >> l >> r;
l--;
cout << la.get(l, r - l - 1, t) << '\n';
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 29ms
memory: 3908kb
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
Wrong Answer
time: 168ms
memory: 18216kb
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:
1737465403 -878638185 -1419808236 489131033 -912107822 -1015472048 798718486 101726012 -927208405 352297170 1835120341 599819007 -465371418 902397800 -2095456551 1230218616 1309123519 -298928732 -485516250 -435762595 484367741 569995372 1507692034 -686309986 -763966629 31350422 -900800492 1705037545...
result:
wrong answer 1st lines differ - expected: '152061320763', found: '1737465403'
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: 509ms
memory: 28452kb
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: 498ms
memory: 28236kb
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: 533ms
memory: 28248kb
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: 498ms
memory: 28468kb
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: 518ms
memory: 28380kb
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: 0
Wrong Answer
time: 88ms
memory: 16592kb
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:
1757912356 -1084053116 81784704 98905 1724299428 -1337638238 122184230 -1255627328 -1304698362 -2018956921 2036265557 1794349578 117294019 300284111 695776684 -913553448 -239486383 -704778319 2130555618 -104600127 -569649259 1832980867 160647082 438592292 -1712090337 4586484 985006134 71394762 -1640...
result:
wrong answer 1st lines differ - expected: '10347846948', found: '1757912356'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%