제출 #1126684

#제출 시각아이디문제언어결과실행 시간메모리
1126684Szymon_PilipczukFountain (eJOI20_fountain)C++20
100 / 100
609 ms40716 KiB
#include <bits/stdc++.h> using namespace std; int main() { priority_queue<vector<int>> pq; int n,p; cin>>n>>p; int c[n+1]; int r[n+1]; long long j[n+1][21][2]; for(int i = 0;i<n;i++) { cin>>r[i]; cin>>c[i]; pq.push({-1*r[i],i}); j[i][0][1] = c[i]; while(pq.top()[0]*-1 < r[i]) { j[pq.top()[1]][0][0] = i; pq.pop(); } } while(!pq.empty()) { j[pq.top()[1]][0][0] = n; pq.pop(); } j[n][0][0] = n; j[n][0][1] = 1e9; for(int i = 1;i<21;i++) { for(int q = 0;q<n+1;q++) { j[q][i][0] = j[j[q][i-1][0]][i-1][0]; j[q][i][1] = j[q][i-1][1] + j[j[q][i-1][0]][i-1][1]; } } for(int i = 0;i<p;i++) { int s; long long a; cin>>s>>a; s--; for(int q = 20;q>=0;q--) { if(a - j[s][q][1] >0) { //cout<<q<<"\n"; a -=j[s][q][1]; s = j[s][q][0]; } } if(s == n) { cout<<0<<"\n"; } else { cout<<s+1<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...