#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
vector<long long int>v;
vector<int>orden;
void dfs(int nodo,vector<pair<int,long long int> >&nuevo,vector<int>&grupo,int cc,vector<int>con,int x){
grupo[nodo]=cc;
orden[nodo]=x;
if(nuevo.size()==0){
pair<int,int>p=make_pair(nodo,v[nodo]);
nuevo.push_back(p);
}
else{
pair<int,int>p=make_pair(nodo,v[nodo]+nuevo[nuevo.size()-1].second);
nuevo.push_back(p);
}
if(grupo[con[nodo]]==-1){
dfs(con[nodo],nuevo,grupo,cc,con,x+1);
}
}
int search(int l,vector<pair<int,long long int> >c,int o){
int low=o,hi=c.size(),r=-1,mid;
while(low<=hi){
mid=low+(hi-low)/2;
if((c[mid].second-c[o].second+v[o])>=l){
r=mid;
hi=mid-1;
}
else{
low=mid+1;
}
}
if(r==-1)return 0;
else return c[r].first+1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin>>n>>q;
int vo,r,l;
v.resize(n);
vector<long long int>d(n);
for(int i=0;i<n;i++){
cin>>d[i]>>v[i];
}
vector<int>con(n);
for(int i=0;i<n;i++){
bool b=false;
for(int k=i;k<n;k++){
if(d[i]<d[k]){
con[i]=k;
b=true;
break;
}
}
if(!b)con[i]=-1;
}
vector<vector<pair<int,long long int> > >compo;
vector<int>grupo(n,-1);
int cc=0;
orden.resize(n);
for(int i=0;i<n;i++){
if(grupo[i]==-1){
vector<pair<int,long long int> >nuevo;
dfs(i,nuevo,grupo,cc,con,0);
compo.push_back(nuevo);
cc++;
}
}
for(int i=0;i<q;i++){
cin>>r>>l;
r--;
if(l<=v[r])cout<<r+1<<"\n";
else
cout<<search(l,compo[grupo[r]],orden[r])<<"\n";
}
return 0;
}
Compilation message
fountain.cpp: In function 'int main()':
fountain.cpp:53:9: warning: unused variable 'vo' [-Wunused-variable]
53 | int vo,r,l;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
237 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
