#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const ll INF = 4e18;
/*
you can only go to an l chain after moving at least once on a w chain at most 32 ish times
because of the doubling effect??? or maybe wrong
draw the graph structure separately for w and l
for w chains you keep going until z + Σs[u] < s[v] => Σs[u] - s[v] < -z
for l chains you keep going until z + Σp[u] ≥ s[v] => s[v] - Σp[u] ≤ z
*/
struct SegTree {
int n; vector<ll> st;
SegTree(int n = 0) : n(n), st(4*n, INF) {}
ll query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return INF;
if (ql <= l && r <= qr) return st[i];
int m = l + (r-l) / 2;
return min(query(2*i+1,l,m,ql,qr),query(2*i+2,m,r,ql,qr));
}
ll update(int i, int l, int r, int k, ll v) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = v;
int m = l + (r-l) / 2;
return st[i] = min(update(2*i+1,l,m,k,v),update(2*i+2,m,r,k,v));
}
ll query(int l, int r) {
return query(0,0,n,l,r+1);
}
void update(int k, ll v) {
update(0,0,n,k,v);
}
int first_less(int i, int l, int r, int ql, int qr, ll x) {
if (qr <= l || r <= ql) return -1;
if (st[i] >= x) return -1;
if (l + 1 == r) return l;
int m = l + (r-l) / 2;
int left = first_less(2*i+1, l, m, ql, qr, x);
if (left != -1) return left;
return first_less(2*i+2, m, r, ql, qr, x);
}
int first_less(int l, int r, ll x) {
return first_less(0, 0, n, l, r, x);
}
};
int n;
vi s,p,w,l;
vvi wchain, lchain;
vector<vector<ll>> wsum, lsum;
vi seen, lc, wc, lp, wp;
vector<SegTree> wst, lst;
void init(int N, vi S, vi P, vi W, vi L) {
n=N,s=S,p=P,w=W,l=L;
seen.assign(n+1, 0);
lc.assign(n+1, 0);
wc.assign(n+1, 0);
lp.assign(n+1, 0);
wp.assign(n+1, 0);
auto process = [](int n, vi &w, vi &gain, vi &seen, vi &wc, vi &wp, vvi &wchain, vector<vector<ll>> &wsum, vector<SegTree> &wst, bool isl) {
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
int id = wc[i] = wchain.size();
wp[i] = 0;
seen[i] = 1;
wchain.push_back(vi(1, i));
wsum.push_back(vector<ll>(1, 0));
ll running = gain[i];
vector<ll> values(1, isl ? s[i] : -s[i]);
int u = w[i];
while (!seen[u] && u != n) {
wsum.back().push_back(running);
values.push_back(isl ? s[u] - running : running - s[u]);
seen[u] = 1; wc[u] = id; wp[u] = wchain.back().size();
wchain.back().push_back(u);
running += gain[u];
u = w[u];
}
wsum.back().push_back(running);
wst.push_back(SegTree(values.size()));
for (int i = 0; i < values.size(); i++) wst.back().update(i, values[i]);
}
};
seen.assign(n+1, 0);
process(n, w, s, seen, wc, wp, wchain, wsum, wst, false);
seen.assign(n+1, 0);
process(n, l, p, seen, lc, lp, lchain, lsum, lst, true);
}
int first_w_bad(int id, int pos, ll z) {
int len = wchain[id].size();
ll threshold = wsum[id][pos] - z;
int res = wst[id].first_less(pos, len, threshold);
return res == -1 ? len : res;
}
int first_l_bad(int id, int pos, ll z) {
int len = lchain[id].size();
ll threshold = z - lsum[id][pos];
int res = lst[id].first_less(pos, len, threshold + 1);
return res == -1 ? len : res;
}
ll simulate(int x, int Z) {
ll z = Z;
while (x != n) {
if (z >= s[x]) {
int id = wc[x], pos = wp[x];
int len = wchain[id].size();
int bad = first_w_bad(id, pos, z);
if (bad == len) {
z += wsum[id][len] - wsum[id][pos];
x = w[wchain[id][len - 1]];
} else {
z += wsum[id][bad] - wsum[id][pos];
x = wchain[id][bad];
}
// for (int i = pos; i < wchain[id].size(); i++) {
// if (z < s[wchain[id][i]]) break;
// z += s[wchain[id][i]]; x = w[x];
// }
// z += s[x];
// x = w[x];
} else {
int id = lc[x], pos = lp[x];
int len = lchain[id].size();
int bad = first_l_bad(id, pos, z);
if (bad == len) {
z += lsum[id][len] - lsum[id][pos];
x = l[lchain[id][len - 1]];
} else {
z += lsum[id][bad] - lsum[id][pos];
x = lchain[id][bad];
}
// for (int i = pos; i < lchain[id].size(); i++) {
// if (z >= s[lchain[id][i]]) break;
// z += p[lchain[id][i]]; x = l[x];
// }
// z += p[x];
// x = l[x];
}
}
return z;
}
