#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int maxn = 1e5 + 69;
const int lg = 17;
int up[maxn][lg], sm[maxn][lg];
vector<int> g[maxn];
vector<int> d(maxn), l(maxn), vis(maxn);
int n, q;
void dfs(int v) {
vis[v] = true;
if(!g[v].empty()) {
dfs(g[v].front());
up[v][0] = g[v].front();
sm[v][0] = l[g[v].front()];
for(int i = 1;i < lg;i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
sm[v][i] = sm[v][i - 1] + sm[up[v][i - 1]][i - 1];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--) {
cin >> n >> q;
for(int i = 1;i <= n;i++)
cin >> d[i] >> l[i];
l[n + 1] = 1e9;
vector<pair<int, int>> st;
st.push_back({1e9, n + 1});
for(int i = n;i >= 1;i--) {
while(!st.empty() && st.back().f < d[i])
st.pop_back();
if(!st.empty())
g[i].push_back(st.back().s);
st.push_back({d[i], i});
}
for(int i = 1;i <= n;i++)
if(!vis[i])
dfs(i);
for(int i = 0;i < q;i++) {
int v, r;
cin >> v >> r;
int u = v;
if(r > l[v]) {
r -= l[v];
for(int j = lg - 1;j >= 0;j--) {
if(sm[u][j] <= r) {
r -= sm[u][j];
u = up[u][j];
if(l[u] >= r)
break;
else
r -= l[u];
}
}
if(r > 0)
u = up[u][0];
}
if(u == n + 1)
u = 0;
cout << u << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
3924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
23936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3796 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
3924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
