Submission #1258091

#TimeUsernameProblemLanguageResultExecution timeMemory
1258091E_rKFountain (eJOI20_fountain)C++20
100 / 100
287 ms56320 KiB
#include <bits/stdc++.h> #define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false) #define pb push_back #define ppb pop_back #define fi first #define se second #define sp " " #define endl "\n" #define mod 1000000007 #define MAXN 500005 #define MAXM 1000006 #define inf 1e18 #define INF 0x3f #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define debug(x) for(auto& a: x) cout << a << " " using namespace std; typedef long long int lo; lo n,m,q,k,a,b; lo arr[MAXN],dia[MAXN],vis[MAXN]; vector<lo> v[MAXN]; lo binlift[MAXN][33]; lo sub[MAXN]; void dfs(lo node, lo ata){ // cout << node << sp << ata << sp << dia[node] << endl; if(node == n+1) return; if(vis[node]) return; vis[node] = 1; sub[node] = arr[node]; for(auto go: v[node]){ if(go != ata) dfs(go,node); sub[node] += sub[go]; binlift[node][0] = go; for (int i = 1; i < 32; ++i) { binlift[node][i] = binlift[binlift[node][i-1]][i-1]; } } } void solve(){ cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> dia[i] >> arr[i]; } vector<pair<lo,lo>> vec; vec.pb({dia[n],n}); v[n].pb(n+1); for (int i = n-1; i > 0; i--) { while(vec.size() and vec.back().fi <= dia[i]){ vec.pop_back(); } if(vec.size() == 0){ v[i].pb(n+1); vec.pb({dia[i],i}); } else{ v[i].pb(vec.back().se); vec.pb({dia[i],i}); } } for (int i = 1; i <= n; ++i) { if(!vis[i]) dfs(i,0); // cout << endl; } // for (int i = 1; i <= n; ++i) // { // cout<<"sub: " << i << sp << sub[i] << endl; // } // for (int i = 1; i < n; ++i) // { // cout << i << ": "; // for (int j = 0; j < 3; ++j) // { // cout << binlift[i][j] << sp; // } // cout << endl; // } while(q--){ lo a,b; cin >> a >> b; if(sub[a] < b){ cout << 0 << endl; continue; } lo kalan = sub[a] - b; for (int i = 32; i >= 0; i--) { if(sub[binlift[a][i]] > kalan){ a = binlift[a][i]; } } cout << a << endl; } } int main() { // cout << fixed << setprecision(12); // freopen("feast.in","r",stdin); // freopen("feast.out","w",stdout); fast; int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...