#include <iostream> #include <vector> #include "dungeons" using namespace std; #define ll long long vector<int> w, l, s, p; vector<vector<pair<ll, pair<int, ll>>>> nextLoss; int n; void init(int n1, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1){ n = n1; s = s1; p = p1; w = w1; l = l1; nextLoss.assign(n+1, {}); nextLoss[n].push_back({20000000000000000, {n, 0}}); for(int i = n-1; i>=0; i--){ nextLoss[i].push_back({(ll)s[i]-1, {l[i], (ll)s[i]}}); int stIndx = lower_bound(nextLoss[w[i]].begin(), nextLoss[w[i]].end(), make_pair((ll)2*s[i], make_pair((int)0, (ll)0))) - nextLoss[w[i]].begin(); while(stIndx < nextLoss[w[i]].size()){ nextLoss[i].push_back({ ((nextLoss[w[i]][stIndx].first != 20000000000000000) ? ((ll)nextLoss[w[i]][stIndx].first - (ll)s[i]):20000000000000000), {nextLoss[w[i]][stIndx].second.first, (ll)s[i]+nextLoss[w[i]][stIndx].second.second}}); stIndx++; } } } ll simulate(int x, int z1){ ll z = (ll)z1; while(x<n){ pair<ll, pair<int, ll>> ind = nextLoss[x][lower_bound(nextLoss[x].begin(), nextLoss[x].end(), make_pair(z, make_pair((int)0, (ll)0))) - nextLoss[x].begin()]; x = ind.second.first; z += ind.second.second; } return z; } // int main(void){ // freopen("input.txt", "r", stdin); // int n1; // vector<int> s1; vector<int> p1; vector<int> w1; vector<int> l1; // cin>>n1; // s1.assign(n1, 0); // l1.assign(n1, 0); // w1.assign(n1, 0); // p1.assign(n1, 0); // for(int i = 0; i<n1; i++) cin>>s1[i]; // for(int i = 0; i<n1; i++) cin>>p1[i]; // for(int i = 0; i<n1; i++) cin>>w1[i]; // for(int i = 0; i<n1; i++) cin>>l1[i]; // init(n1, s1, p1, w1, l1); // int q; cin>>q; // for(int i = 0; i<q; i++){ // int x2, z2; // cin>>x2>>z2; // cout<<simulate(x2, z2)<<endl; // } // }