#include <bits/stdc++.h>
using namespace std;
#define debug(var) cerr<<"#"<<#var<<"="<<var<<endl;
#define int long long
const int LOG = 18;
const int MAXI = 2*100000;
struct Recip{
int diametre;
int capacite;
int id;
void read(int i){
cin>>diametre;
cin>>capacite;
id=i;
};
};
vector<Recip> recipient;
vector<int> links[MAXI];
int sumFromRoot[MAXI];
int up[MAXI][LOG];
int n,q;
void dfs(int node,int somme=0){
somme+=recipient[node].capacite;
sumFromRoot[node] = somme;
for(int&v:links[node]){
dfs(v,somme);
}
}
int ancestorK(int node,int k){
for(int log=LOG-1;log>=0;log--){
if((k>>log)&1){
node = up[node][log];
}
}
return node;
}
int solve2(int id,int volume){
int sommeChaine = sumFromRoot[id];
if(sommeChaine<volume){
return -1;
}
int low=0;
int high=n-1;
while((high-low)>1){
int mid = (low+high)/2;
int pos = ancestorK(id,mid);
if(pos==-1){
high=mid;
continue;
}
int somme = sommeChaine-sumFromRoot[pos]+recipient[pos].capacite;
if(somme>volume){
high = mid;
}else if(somme<volume){
low = mid;
}else{
return pos;
}
}
int LS = sommeChaine-sumFromRoot[ancestorK(id,low)]+recipient[ancestorK(id,low)].capacite;
if(LS>=volume){
return ancestorK(id,low);
}else{
return ancestorK(id,high);
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
recipient.resize(n);
vector<int> pref(n);
int act=0;
for(int i = 0 ; i <n;i++){
recipient[i].read(i);
act+=recipient[i].capacite;
pref[i]=act;
}
int papa[n];
for(int i = 0;i<n;i++){
papa[i]=-1;
}
stack<Recip> pile;
for(int i = 0;i<n;i++){
while(!pile.empty() && recipient[i].diametre>pile.top().diametre){
papa[pile.top().id] = i;
links[i].push_back(pile.top().id);
pile.pop();
}
pile.push(recipient[i]);
}
for(int i = 0 ; i<n;i++){
if(papa[i]==-1){
dfs(i);
}
up[i][0]=papa[i];
}
for(int l=1;l<LOG;l++){
for(int i=0;i<n;i++){
if(up[i][l-1]==-1){
up[i][l]=-1;
}else{
up[i][l] = up[up[i][l-1]][l-1];
}
}
}
for(int i = 0 ; i < q;i++){
int id,volume;cin>>id>>volume;
id--;
cout<<solve2(id,volume)+1<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
57296 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
