Submission #1182450

#TimeUsernameProblemLanguageResultExecution timeMemory
1182450meicrisFountain (eJOI20_fountain)C++17
0 / 100
38 ms12360 KiB
#include<bits/stdc++.h> using namespace std; vector<long> dmt,cap; vector<vector<int>> sgtf,sgtv; int aux; long query(long a,long b) { aux=0; if(b<=sgtv[a][0]) return a; else {while(b>sgtv[a][aux]&&sgtv[a][aux]!=*sgtv[a].end()) { sgtv[a][aux++]; } if(sgtv[a][aux]==*sgtv[a].end()) return sgtf[a][*prev(sgtf[a].end())]; else return sgtf[a][aux-1]; } } void solve() { long n,q; cin>>n>>q; dmt.assign(n+2,1e5+10); cap.assign(n+1,1e5+10); sgtf.resize(n+2,vector<int> (1,0)); sgtv.resize(n+2,vector<int> (1,0)); long a,b; for(int i=1; i<=n; i++) { cin>>a>>b; dmt[i]=a,cap[i]=b; } stack<long> pila; pila.push(0); for(int i=n; i>=1; i--) { //pila.push(i+1); sgtv[i][0]=cap[i]; /*if(dmt[pila.top()]==0) { sgtf[i][0]=0, pila.pop(); } else {*/ /*if(dmt[i]<dmt[pila.top()]) sgtf[i][0]=pila.top(); else {*/ while(dmt[i]>=dmt[pila.top()]) { pila.pop(); } //if(pila.empty()) //sgtf[i][0]=0; //else sgtf[i][0]=pila.top(); pila.push(i); //} //} } /*for(int i=1;i<=n;i++){ cout<<sgtf[i][0]<<" ----------- "<<sgtv[i][0]<<endl; }*/ int s; for(int i=1;i<=n;i++) { s=i; while(s){ s=sgtf[s][0]; sgtf[i].push_back(sgtf[s][0]); } s=sgtv[i][0]; for(auto x:sgtf[i]) { sgtv[i].push_back(s+sgtv[x][0]); s+=sgtv[x][0]; } } while(q--) { cin>>a>>b; cout<<query(a,b)<<endl; } } int main() { solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...