#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;
vector <int> a(N), b(N), d(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), sum = up;
void dfs(int v, int pr, int h = 0){
d[v] = h+1;
up[v][0] = pr;
for (auto to : g[v]){
dfs(to.ff, v, h+1);
sum[to.ff][0] = to.ss;
}
}
int get(int r, int v){
for (int j = 19; j >= 0; --j){
if (sum[r][j] < v){
v -= sum[r][j];
r = up[r][j];
}
}
return r;
}
void solve(){
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
set <pii> st; st.insert({inf, 0});
for (int i = 1; i <= n; ++i) st.insert({a[i], i});
for (int i = 1; i <= n; ++i){
pii v = *st.upper_bound({a[i], inf});
g[v.ss].pb({i, b[i]});
st.erase({a[i], i});
}
for (int i = 0; i <= n; ++i)
if (!d[i]) dfs(i, i);
for (int j = 1; j < 20; ++j)
for (int i = 0; i <= n; ++i) up[i][j] = up[up[i][j-1]][j-1];
for (int j = 1; j < 20; ++j)
for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
while (q--){
int r, v;
cin >> r >> v;
cout << get(r, v) << '\n';
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int tt = 1;
//cin >> tt;
while (tt--){
solve();
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
88024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
378 ms |
102260 KB |
Output is correct |
| 2 |
Correct |
407 ms |
101660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
88024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
