#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int par[20][200005], n, q, sm[20][200005], A[200005], D[200005];
void solve(){
cin >> n >> q;
for(int i=1;i<=n;i++)cin >> D[i] >> A[i];
A[n + 1] = 1e10;
D[n + 1] = 1e10;
stack <int> s;
s.push(n + 1);
for(int i=n;i>=1;i--){
while(!s.empty() && D[s.top()] <= D[i])s.pop();
par[0][i] = s.top(); sm[0][i] = A[i] + A[s.top()];
s.push(i);
}
par[0][n+1] = n + 1; sm[0][n+1] = 1e10;
for(int i=1;i<=19;i++)for(int j=1;j<=n+1;j++){
par[i][j] = par[i-1][par[i-1][j]];
sm[i][j] = sm[i-1][j] + sm[i-1][par[i-1][j]] - A[par[i-1][j]];
assert(sm[i][j] >= 0);
}
while(q--){
int x, v; cin >> x >> v;
if(v <= A[x]){
cout << x << '\n';
continue;
}
int cur = x;
for(int i = 19; i >= 0; i--){
if(sm[i][cur] < v){
v -= sm[i][cur];
cur = par[i][cur];
}
}
cur = par[0][cur];
cout << (cur == n + 1 ? 0 : cur) << '\n';
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
fountain.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
52 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
63832 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
63836 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
311 ms |
66568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
63832 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
63836 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
