Submission #1125123

#TimeUsernameProblemLanguageResultExecution timeMemory
1125123PwoFountain (eJOI20_fountain)C++20
100 / 100
253 ms31352 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n, q; pair<int, int> a[100005]; vector<int> g[100005]; int pre[100005],up[100005][20]; void dfs(int v) { for (const int u : g[v]) { pre[u] = pre[v] + a[u].second; up[u][0] = v; for (int i = 1; i < 17; i++) up[u][i] = up[up[u][i - 1]][i - 1]; dfs(u); } } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second; vector<int> v; for (int i = 1; i <= n; i++) { while (!v.empty() && a[v.back()].first < a[i].first) { g[i].push_back(v.back()); v.pop_back(); } v.push_back(i); } for (const int u : v) g[0].push_back(u); dfs(0); while (q--) { int r, v; cin >> r >> v; v--; int cur = r; for (int i = 16; i >= 0; i--) if (pre[r] - pre[up[cur][i]] <= v) cur = up[cur][i]; cout << cur << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...