Submission #1182460

#TimeUsernameProblemLanguageResultExecution timeMemory
1182460meicrisFountain (eJOI20_fountain)C++17
0 / 100
43 ms24136 KiB
#include<bits/stdc++.h> using namespace std; const int LG=1e10; 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+1,1e5+10); cap.assign(n+1,1e5+10); sgtf.resize(n+1,vector<int> (20,0)); sgtv.resize(n+1,vector<int> (20,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--) { sgtv[i][0]=cap[i]; while(dmt[i]>=dmt[pila.top()]) { pila.pop(); } sgtf[i][0]=pila.top(); pila.push(i); } for(int j=1; j<20; j++) for(int i=1; i<n+1; i++) { int parent=sgtf[i][j-1]; sgtv[i][j]=sgtv[i][j-1]+sgtv[parent][j-1]; sgtf[i][j]=sgtf[parent][j-1]; } /*for(int i=1;i<=n;i++){ for(int j=0;j<=n;j++){ cout<<sgtv[i][j]<<" "; } cout<<endl; }*/ while(q--) { cin>>a>>b; cout<<query(a,b)<<endl; } } int main() { solve(); }

Compilation message (stderr)

fountain.cpp:3:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
    3 | const int LG=1e10;
      |              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...