Submission #383727

#TimeUsernameProblemLanguageResultExecution timeMemory
383727MODDIFountain (eJOI20_fountain)C++14
100 / 100
903 ms19040 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define vi vector<int> #define vl vector<ll> #define mp make_pair #define pb push_back using namespace std; const int MAXN = 100050; const int LOG = 20; int diameter[MAXN], liters[MAXN], up[MAXN][LOG], sum[MAXN][LOG]; int main(){ int n, q; cin>>n>>q; for(int i = 1; i <= n; i++){ cin>>diameter[i]>>liters[i]; } priority_queue<pii> pq; for(int i = 1; i <= n; i++){ while(!pq.empty() && -pq.top().first < diameter[i]) up[pq.top().second][0] = i, pq.pop(); pq.push({-diameter[i], i}); } while(!pq.empty()) up[pq.top().second][0] = 0, pq.pop(); for(int i = 1; i <= n; i++) sum[i][0] = liters[i]; for(int j = 1; j < LOG; j++){ for(int i = 0; i <= n; i++){ up[i][j] =up[up[i][j-1]][j-1]; sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1]; } } while(q--){ int a, b; cin>>a>>b; for(int j = LOG - 1; j >= 0; j--){ if(sum[a][j] >= b) continue; b -= sum[a][j]; a = up[a][j]; } cout<<a<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...