#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(c) (c).begin(), (c).end()
#define MIN(a, b) ((a) = min((a), (b)))
#define MAX(a, b) ((a) = max((a), (b)))
const ll MOD = 1e9+7;
const int abc = 'z'-'a'+1;
int n, q;
vector<ll> d, c;
vector<ll> p;
vector<array<pair<ll,int>, 19>> v;
// v[i][j] = i. medencebol indulva 2^j-t lemenve (a faban) {mennyi viz kell, melyik medence}
// v[n][barmi] = {1e9+1, n};
int query(int i, ll w){
if(w <= c[i]) return i;
int j = 0;
while(v[i][j].first <= w)j++;
j--;
return query(v[i][j].second, w-v[i][j].first);
}
void solve(){
cin>>n>>q;
d.resize(n); c.resize(n);
for(int i = 0; i < n; i++){
cin>>d[i]>>c[i];
}
p.assign(n, 0);
stack<int> s;
for(int i = n-1; i >= 0; i--){
while(!s.empty() && d[s.top()] <= d[i]){
s.pop();
}
if(s.empty()) p[i] = n;
else p[i] = s.top();
s.push(i);
}
v.assign(n+1, array<pair<ll,int>, 19>());
for(int i = 0; i < 19; i++){
v[n][i] = {1e17+1, n};
}
for(int i = n-1; i >= 0; i--){
if(p[i] == n){
for(int j = 0; j < 19; j++){
v[i][j] = {1e17+1, n};
}
continue;
}
v[i][0] = {c[i], p[i]};
for(int j = 1; j < 19; j++){
if(v[i][j-1].second == n){
v[i][j] = {1e17+1, n};
continue;
}
if(v[ v[i][j-1].second ][j-1].second == n){
v[i][j] = {1e17+1, n};
continue;
}
v[i][j].first = v[i][j-1].first + v[ v[i][j-1].second ][j-1].first;
v[i][j].second = v[ v[i][j-1].second ][j-1].second;
}
}
while(q--){
int a, b; cin>>a>>b; a--;
int r = query(a, b);
cout<<(r+1)%(n+1)<<endl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int _t;
_t = 1;
while(_t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
425 ms |
34884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
