| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1021096 | awu | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
out << "(" << p.f << ", " << p.s << ")";
return out;
}
template<typename T>
typename enable_if<!is_same<T, const char *>::value && !is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T o) {
out << "{";
int g = o.size();
for(auto i : o) out << i << (--g ? ", " : "");
out << "}";
return out;
}
// void my_assert(bool b) {
// if(!b) {
// cerr << "Assertion failed" << endl;
// *((volatile int*)0);
// }
// }
// #undef assert
// #define assert my_assert
int millis() {
return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
}
int pt = 0;
int start_time;
void pstart() {
start_time = millis();
}
void pend() {
pt += millis() - start_time;
}
int n;
vector<signed> s, p, w, l;
vector<vector<vector<int>>> jmp, mx;
vector<vector<vector<int>>> prec; // mx is exc
int nk = 25;
int jl = 20;
void init(signed N, vector<signed> S, vector<signed> P, vector<signed> W, vector<signed> L) {
pstart();
n = N;
s = S;
p = P;
w = W;
l = L;
jmp = mx = vector<vector<vector<int>>>(nk, vector<vector<int>>(n + 1, vector<int>(jl)));
prec = vector<vector<vector<int>>>(nk, vector<vector<int>>(n + 1, vector<int>(jl)));
for(int i = 0; i < nk; i++) {
for(int j = 0; j < n; j++) {
if((1 << i) >= s[j]) {
jmp[i][j][0] = w[j];
prec[i][j][0] = s[j];
mx[i][j][0] = inf;
} else {
jmp[i][j][0] = l[j];
prec[i][j][0] = p[j];
mx[i][j][0] = s[j];
}
}
fill(all(jmp[i][n]), n);
fill(all(mx[i][n]), inf);
for(int k = 1; k < jl; k++) {
for(int j = 0; j < n; j++) {
jmp[i][j][k] = jmp[i][jmp[i][j][k - 1]][k - 1];
prec[i][j][k] = prec[i][j][k - 1] + prec[i][jmp[i][j][k - 1]][k - 1];
mx[i][j][k] = min(mx[i][j][k - 1], (int)max(0ll, mx[i][jmp[i][j][k - 1]][k - 1] - prec[i][j][k - 1]));
}
}
}
pend();
assert(pt < 2000);
}
int fastlog2(int x) {
return 63 - __builtin_clzll(x);
}
int simulate(signed x, signed Z) {
int z = Z;
int li = -1;
int icnt = 0;
while(x != n) {
icnt++;
// assert(icnt < 40);
if(z >= s[x]) {
z += s[x];
x = w[x];
} else {
z += p[x];
x = l[x];
}
int i = fastlog2(z);
assert(z >= 1e7 || i > li);
li = i;
i = min(i, nk - 1);
for(int k = jl - 1; k >= 0; k--) {
if(z < mx[i][x][k]) {
z += prec[i][x][k];
x = jmp[i][x][k];
if(x == n) break;
}
}
// assert(x == n || z >= s[x]);
}
return z;
}
signed main() {
int n, q; cin >> n >> q;
vector<signed> s(n), p(n), w(n), l(n);
for(int i = 0; i < n; i++) cin >> s[i];
for(int i = 0; i < n; i++) cin >> p[i];
for(int i = 0; i < n; i++) cin >> w[i];
for(int i = 0; i < n; i++) cin >> l[i];
init(n, s, p, w, l);
while(q--) {
int x, z; cin >> x >> z;
cout << simulate(x, z) << endl;
}
}