Submission #1222380

#TimeUsernameProblemLanguageResultExecution timeMemory
1222380Robert_juniorFountain (eJOI20_fountain)C++20
0 / 100
58 ms32580 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define ins insert #define pb push_back #define F first #define S second const int N = 2e5+4, M = 5e5 + 7; const int mod = 1e9 + 7; int up[N][20], up1[N][20]; int c[N], d[N]; void solve(){ int n, q; cin>>n>>q; for(int i = 1; i <= n; i++){ cin>>d[i]>>c[i]; } stack<int>s; for(int i = n; i >= 1; i--){ while(s.size() && d[s.top()] <= d[i]){ s.pop(); } if(s.size()) up[i][0] = s.top(); else up[i][0] = 0; s.push(i); up1[i][0] = c[up[i][0]]; } for(int i = 1; i <= n; i++){ for(int j = 1; j < 20; j++){ up[i][j] = up[up[i][j - 1]][j - 1]; up1[i][j] = up1[i][j - 1] + up1[up[i][j - 1]][j - 1]; } } while(q--){ int v, a; cin>>v>>a; a -= c[v]; for(int i = 19; i >= 0; i--){ if(a >= up1[v][i]){ a -= up1[v][i]; v = up[v][i]; } } if(a >= 1) v = up[v][0]; if(v < 1 || v > n) cout<<0<<'\n'; else cout<<v<<'\n'; } } main(){ ios_base :: sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin>>t; for(int i = 1; i <= t; i++){ //cout<<"Case "<<i<<": "; solve(); } }

Compilation message (stderr)

fountain.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...