#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int N, Q;
vector<int> D, C, next_bigger;
void preprocess_next_bigger() {
next_bigger.assign(N, 0);
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();
} else {
next_bigger[i] = -1;
}
s.push(i);
}
}
int pour(int idx, int V) {
while (true) {
if (V <= C[idx]) {
return idx + 1;
}
V -= C[idx];
idx = next_bigger[idx];
if (idx == -1) return 0;
}
}
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();
for (int i = 0; i < Q; ++i) {
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... |