#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Tree {
int sz = 1;
vector<vector<int>> table;
vector<vector<ll>> sum;
Tree (){}
Tree (int n) {
while ((1 << sz) <= n) sz++;
table = vector<vector<int>> (sz, vector<int> ((1 << sz)));
sum = vector<vector<ll>> (sz, vector<ll> ((1 << sz)));
}
void add_cost(int u, int x) {
sum[0][u] = x;
}
void add_edge(int u, int v) {
table[0][u] = v;
}
void build() {
for (int bit = 1; bit < sz; ++bit) {
for (int Node = 1; Node < sz; ++Node) {
int to = table[bit - 1][Node];
table[bit][Node] = table[bit - 1][to];
sum[bit][Node] = sum[bit - 1][Node] + sum[bit - 1][to];
}
}
}
pair<int, ll> get_kth(int Node, int k) {
ll ret = 0;
for (int i = sz - 1; i >= 0; --i) {
if (k & (1 << i)) {
ret += sum[i][Node];
Node = table[i][Node];
}
}
return make_pair(Node, ret + sum[0][Node]);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q, idx = 1;
cin >> n >> q;
Tree tree(n);
vector<pair<int, int>> v(n);
for (auto &[a, b] : v) {
cin >> a >> b;
tree.add_cost(idx++, b);
}
vector<int> track;
for (int i = n - 1; i >= 0; --i) {
while (track.size() && v[track.back()].first <= v[i].first) {
track.pop_back();
}
if (track.size()) {
tree.add_edge(i + 1, track.back() + 1);
}
track.push_back(i);
}
tree.build();
for (int i = 0, start, x; i < q; ++i) {
cin >> start >> x;
int l = 0;
int r = n - start;
int best = 0;
while (l <= r) {
int mid = (l + r) / 2;
auto [who, path] = tree.get_kth(start, mid);
if (path >= x) {
best = who;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << best << '\n';
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
31588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
