Submission #466702

#TimeUsernameProblemLanguageResultExecution timeMemory
466702Clan328Fountain (eJOI20_fountain)C++17
100 / 100
531 ms46944 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define nL '\n' #define all(x) (x).begin(), (x).end() typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<pll> vpll; vvl up; vvl sum; int main() { #ifdef LOCAL freopen("io/input.txt", "r", stdin); freopen("io/output.txt", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); ll n, q; cin >> n >> q; vpll input(n+1); for (int i = 1; i <= n; i++) cin >> input[i].first >> input[i].second; ll LOG = 19; up = vvl(n+2, vl(LOG+1)); sum = vvl(n+2, vl(LOG+1)); stack<ll> stk; for (int i = n; i > 0; i--) { while (!stk.empty() && input[stk.top()].first <= input[i].first) stk.pop(); if (!stk.empty()) up[i][0] = stk.top(); else up[i][0] = n+1; sum[i][0] = input[i].second; stk.push(i); } sum[n+1][0] = 1e18; for (ll j = 1; j < LOG; j++) { sum[n+1][j] = 1e18; for (ll v = 1; v <= n; v++) { up[v][j] = up[up[v][j-1]][j-1]; sum[v][j] = sum[v][j-1] + sum[up[v][j-1]][j-1]; } } while (q--) { ll r; ll v; cin >> r >> v; for (ll i = LOG-1; i >= 0; i--) { if (sum[r][i] < v) { v -= sum[r][i]; r = up[r][i]; } } cout << (r <= n? r : 0) << nL; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...