#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int LOG = 20;
int N, Q;
vector<int> D, C, next_bigger;
int jump[MAXN][LOG];
int sum[MAXN][LOG];
void preprocess_next_bigger() {
next_bigger.assign(N, -1);
stack<int> s;
for (int i = N - 1; i >= 0; --i) {
while (!s.empty() && D[i] >= D[s.top()]) {
s.pop();
}
if (!s.empty()) {
next_bigger[i] = s.top();
}
s.push(i);
}
}
void build_binary_lifting() {
for (int i = 0; i < N; ++i) {
jump[i][0] = next_bigger[i];
sum[i][0] = C[i];
}
for (int k = 1; k < LOG; ++k) {
for (int i = 0; i < N; ++i) {
int nxt = jump[i][k - 1];
if (nxt == -1) {
jump[i][k] = -1;
sum[i][k] = sum[i][k - 1];
} else {
jump[i][k] = jump[nxt][k - 1];
sum[i][k] = sum[i][k - 1] + sum[nxt][k - 1];
}
}
}
}
int pour(int idx, int V) {
if (V <= C[idx]) return idx + 1;
V -= C[idx];
for (int k = LOG - 1; k >= 0; --k) {
if (jump[idx][k] != -1 && sum[idx][k] < V) {
V -= sum[idx][k];
idx = jump[idx][k];
}
}
idx = jump[idx][0];
if (idx == -1 || V > C[idx]) return 0;
return idx + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
D.resize(N);
C.resize(N);
for (int i = 0; i < N; ++i) {
cin >> D[i] >> C[i];
}
preprocess_next_bigger();
build_binary_lifting();
while (Q--) {
int R, V;
cin >> R >> V;
cout << pour(R - 1, V) << '\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... |