QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520947 | #8649. Escape Route 2 | green_gold_dog# | 0 | 622ms | 48312kb | C++20 | 4.3kb | 2024-08-15 18:00:16 | 2024-08-15 18:00:16 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, 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));
ll lst = INF64;
while (!all.empty()) {
ll 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();
}
}
}
ll 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) {
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 * d + ends[v - 1][t];
}
ll 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++;
}
ll 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: 30ms
memory: 3864kb
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: 150ms
memory: 18456kb
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:
150656125631 362085789277 100254211736 511669621157 270452811292 113543449812 76000337116 547749747202 165171321007 264532476824 34087066011 246897531911 11716932904 162705959916 605682106783 369192210940 97282981063 349077999276 71123732650 101238257377 24146378819 332064456630 123251353354 2105490...
result:
wrong answer 1st lines differ - expected: '152061320763', found: '150656125631'
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: 0
Wrong Answer
time: 622ms
memory: 48312kb
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:
986847074 210015534 986847074 340291594 376752401 646919150 23398481 76778858 373373643 540095714 113469318 60164999 223458267 426858638 50052816 636734034 220083324 436837938 140224434 36789711 10186037 646784751 83430230 436766837 600181308 293480714 590091050 600200671 450040181 270193472 1034634...
result:
wrong answer 1st lines differ - expected: '996840913', found: '986847074'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%