This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
const int inf = 1e18;
const int lg = 18;
vector<int>g[N];
int up[N][lg],sm[N][lg],vis[N];
pair<int,int>a[N];
void dfs(int x,int par) {
vis[x] = 1;
for(auto X:g[x]) {
if(X != par) {
dfs(X,x);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,Q;
cin >> n >> Q;
for(int i=1;i<=n;i++) cin >> a[i].F >> a[i].S;
stack<pair<int,int>>st;
for(int i=1;i<=n;i++) up[i][0] = i;
for(int i=n;i>=1;i--) {
while(st.size() && st.top().F <= a[i].F) st.pop();
if(!st.empty()) {
g[i].pb(st.top().S);
up[i][0] = st.top().S;
sm[i][0] = a[st.top().S].S;
// /cout << i << " -> " << st.top().S << ' ' << a[st.top().S].S << endl;
//g[st.top().S].pb(i);
}
st.push({a[i].F,i});
}
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
for(int j=1;j<lg;j++) {
for(int i=1;i<=n;i++) {
up[i][j] = up[up[i][j-1]][j-1];
sm[i][j] = sm[i][j-1]+sm[up[i][j-1]][j-1];
}
}
/*for(int i=1;i<=n;i++) {
for(int j=0;j<lg;j++) cout << sm[i][j] << ' ';
cout << endl;
}*/
while(Q--) {
int index,val;
cin >> index >> val;
val -= a[index].S;
for(int j=lg-1;j>=0;j--) {
if(sm[index][j] <= val) {
//cout << index << ' ' << j << ' ' << val << ' ' << sm[index][j] << endl;
val -= sm[index][j];
index = up[index][j];
}
}
if(val > sm[index][0]) {
cout << "0\n";
continue;
}
if(val > 0) index = up[index][0];
cout << index << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |