Submission #421657

#TimeUsernameProblemLanguageResultExecution timeMemory
421657Aldas25Fountain (eJOI20_fountain)C++14
100 / 100
1150 ms35976 KiB
#include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr) #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second #define pb push_back typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vii; const int MAXN = 500100, MAXK = 20; const ll INF = 1e16; const ll MOD = 1e9+7; int n, q; ll d[MAXN], c[MAXN]; vii srt; set<int> cur; int par[MAXN][MAXK]; ll sum[MAXN][MAXK]; void build () { FOR(i, 1, MAXK-1) { FOR(v, 1, n) { par[v][i] = par[par[v][i-1]][i-1]; sum[v][i] = sum[v][i-1] + sum[par[v][i-1]][i-1]; } } } ll getSum (int v, int i) { ll ret = 0ll; FOR(j, 0, MAXK-1) { if (i & (1<<j)) { ret += sum[v][j]; v = par[v][j]; } } return ret; } int lift (int v, int i) { FOR(j, 0, MAXK-1) if (i & (1<<j)) v = par[v][j]; return v; } int query (int r, ll v) { //cout << " query r = " << r << " v = " << v << endl; int le = 0, ri = n; while (le < ri) { int mid = (le+ri)/2; //cout << " mid = " << mid << " getSum = " << getSum(r, mid+1) << endl; if (getSum(r, mid+1) < v) le = mid+1; else ri = mid; } int ret = lift(r, le); if (ret == n+1) return 0; else return ret; } int main() { FAST_IO; cin >> n >> q; FOR(i, 1, n) { cin >> d[i] >> c[i]; srt.pb({-d[i], i}); sum[i][0] = c[i]; } sum[n+1][0] = 1e9+5; sort(srt.begin(), srt.end()); cur.insert(n+1); for (auto p : srt) { int id = p.s; auto it = cur.upper_bound(id); par[id][0] = (*it); cur.insert(id); } //FOR(i, 1, n) cout << " i=" << i << " to = " << par[i][0] << endl; build (); REP(q) { int r; ll v; cin >> r >> v; cout << query(r,v) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...