#include<bits/stdc++.h>
using namespace std;
vector<int>d, c; /// diameter and capacity
vector<vector<long long>>table, calc;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
d.resize(n + 1);
c.resize(n + 1);
vector<int>next(n + 1), LOG(n + 1);
LOG[1] = 0;
for(int i = 2;i <= n;++i)LOG[i] = LOG[i / 2] + 1;
table.resize(LOG[n] + 1);
calc.resize(LOG[n] + 1);
for(int i = 0;i <= LOG[n];++i){
table[i].resize(n + 1);
calc[i].resize(n + 1);
}
d[0] = 2e9;
c[0] = 2e9;
for(int i = 1;i <= n;++i){
cin >> d[i] >> c[i];
}
stack<int>st;
st.push(0);
for(int i = n;i >= 1;--i){
while(d[st.top()] <= d[i]){
st.pop();
}
next[i] = st.top();
st.push(i);
}
table[0][0] = 0;
for(int i = 0;i <= n;++i){
table[0][i] = next[i];
calc[0][i] = c[next[i]];
}
for(int i = 1;i <= LOG[n];++i){
for(int j = 0;j <= n;++j){
table[i][j] = table[i - 1][table[i - 1][j]];
calc[i][j] = calc[i - 1][j] + calc[i - 1][table[i - 1][j]];
}
}
while(q--){
int node, v;
cin >> node >> v;
int l = 0, r = n + 1, ans = 0;
while(r >= l){
int mid = (l + r) >> 1;
int cpy = mid, cpyn = node;
long long C = 1 + c[node];
// cout << "MID: " << mid << ": \n";
for(int i = LOG[n];i >= 0;--i){
if(cpy >= (1 << i)){
cpy -= (1 << i);
C += calc[i][cpyn];
cpyn = table[i][cpyn];
if(C >= v){
break;
}
// cout << "NODE: " << cpyn << "\n";
}
}
// cout << C << "\n\n";
if(C >= v){
ans = cpyn;
r = mid - 1;
}
else{
l = mid + 1;
}
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
506 ms |
28236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
