제출 #1198282

#제출 시각아이디문제언어결과실행 시간메모리
1198282mishasimFountain (eJOI20_fountain)C++20
100 / 100
152 ms32956 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' long long n,q,val,pos,currd; long long d[100005],v[100005],nextx[100005]; stack<long long> st; using ll = long long; const int MAXN = 100000; const int LOG = 18; ll upper[MAXN+1][LOG]; ll sum[MAXN+1][LOG]; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>q; for(int i = 1 ; i<=n ; i++){ cin>>d[i]>>v[i]; } for(int i = n ; i>=1 ; i--){ while(st.size()>0 && d[st.top()]<=d[i]){ st.pop(); } if(st.size()==0)nextx[i] = 0; else nextx[i] = st.top(); st.push(i); } for(int i = 1 ; i<=n ; i++){ upper[i][0] = nextx[i]; sum[i][0] = v[i]; } for(int k = 1 ; k<=17 ; k++){ for(int i = 1 ; i<=n ; i++){ int p = upper[i][k-1]; if(p==0)upper[i][k] = 0; else upper[i][k] = upper[p][k-1]; sum[i][k] = sum[i][k-1]+(p == 0 ? 0LL : sum[p][k-1]); } } while(q--){ cin>>pos>>val; long long curr = pos; long long rem = val; for(int k = 17 ; k>=0 ; k--){ if(curr!=0 && upper[curr][k] != 0 && sum[curr][k] < rem){ rem-=sum[curr][k]; curr = upper[curr][k]; } } long long answer = 0; if(curr!=0 && v[curr]>=rem){ answer = curr; } else answer = 0; cout<<answer<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...