Submission #404407

#TimeUsernameProblemLanguageResultExecution timeMemory
404407hiderrFountain (eJOI20_fountain)C++14
100 / 100
213 ms11128 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 100000; const int LOG_N = 17; long long sum[MAX_N + 1]; int height[MAX_N + 1], last[MAX_N + 1]; const int NONE = 0; int pointers[MAX_N + 1][LOG_N + 1]; int find_level(int r, long long v, long long required) { int i = 0; while(sum[pointers[r][i]] > required) i++; if(i == 0) return r; return find_level(pointers[r][i-1], v, required); } int main() { cin.tie(0); ios_base::sync_with_stdio(false); int n, q; cin >> n >> q; stack<pair<int, int>> mq; mq.push({ 0, NONE }); for(int i = 1; i <= n; i++) { cin >> height[i] >> sum[i]; } for(int i = n; i >= 1; i--) { pair<int, int> t = mq.top(); while (mq.top().second != NONE && mq.top().first <= height[i]) { mq.pop(); t = mq.top(); } last[i] = t.second; mq.push({height[i], i}); } for(int i = n; i >= 1; i--) { sum[i] += sum[last[i]]; pointers[i][0] = last[i]; for(int j = 1; j <= LOG_N; j++) { pointers[i][j] = pointers[pointers[i][j-1]][j-1]; } } int r; long long v; for(int do_not_use_me = 0; do_not_use_me < q; do_not_use_me++) { cin >> r >> v; long long required = sum[r] - v; if(required < 0) { cout << 0 << '\n'; continue; } cout << find_level(r, v, required) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...