#include <bits/stdc++.h>
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
vector<ll> sparsemax[19];
vector<ll> logovi;
vector<vector<ll> > g;
vector<ll> tren;
vector<ll> lift[19];
vector<ll> sume;
vector<bool> bio;
vector<pii> niz;
ll query(ll l,ll r){
//cout<<l<<" "<<r<<" "<<logovi[r-l+1]<<" "<<l+(1<<logovi[r-l+1])<<" "<<max(sparsemax[logovi[r-l+1]][r],sparsemax[logovi[r-l+1]][l+(1<<logovi[r-l+1])-1])<<"\n";
return max(sparsemax[logovi[r-l+1]][r],sparsemax[logovi[r-l+1]][l+(1<<logovi[r-l+1])-1]);
}
void dfs(ll cvor,ll sum){
if(bio[cvor]) return;
//cout<<cvor<<endl;
sum+=niz[cvor].yy;
//cout<<cvor<<" "<<niz[cvor].yy<<" "<<sum<<"\n";
bio[cvor]=true;
tren.push_back(cvor);
for(ll i:g[cvor]){
if(bio[i]) continue;
dfs(i,sum);
}
//cout<<"proso"<<endl;
for(ll i=0;i<19;i++){
if((1<<i)>=tren.size()) {lift[i][cvor]=-1; continue;}
lift[i][cvor]=tren[(ll)tren.size()-((ll)1<<i)-1];
}
sume[cvor]=sum;
tren.pop_back();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,q;
cin>>n>>q;
niz.resize(n+1);
niz[n]=mp(1e9+1,1e9+1);
for(ll i=0;i<n;i++) {cin>>niz[i].xx>>niz[i].yy;}
logovi.resize(n+1);
ll sta=-1;
ll tren=1;
for(ll i=1;i<=n;i++){
if(tren==i){
tren=2*i;
sta++;
}
logovi[i]=sta;
}
g.resize(n+1);
for(ll i=0;i<19;i++){
sparsemax[i].resize(n+1);
for(ll j=(1<<i)-1;j<=n;j++){
if(i==0) sparsemax[i][j]=niz[j].xx;
else{
sparsemax[i][j]=max(sparsemax[i-1][j],sparsemax[i-1][j-((ll)1<<(i-1))]);
//cout<<i<<" "<<j<<" "<<sparsemax[i][j]<<endl;
}
}
}
for(ll i=0;i<n;i++){
ll l=i;
ll r=n;
ll naj=-1;
while(l<=r){
ll mid=l+(r-l)/2;
//cout<<i<<" "<<mid<<" "<<query(i+1,mid)<<endl;
if(query(i,mid)>niz[i].xx){
naj=mid;
r=mid-1;
}else l=mid+1;
}
//cout<<i<<" "<<naj<<endl;
g[i].pb(naj);
g[naj].pb(i);
}
sume.resize(n+1);
bio.resize(n+1,false);
for(ll i=0;i<19;i++) lift[i].resize(n+1);
dfs(n,0);
//for(ll i=0;i<=n;i++) cout<<sume[i]<<" ";
while(q--){
ll r,v;
cin>>r>>v;
r--;
ll tren=r;
for(ll i=18;i>=0;i--){
if(lift[i][tren]==-1) continue;
if(sume[r]-sume[lift[i][tren]]>=v) continue;
tren=lift[i][tren];
}
if(tren==n) cout<<0<<"\n";
else cout<<tren+1<<"\n";
}
return 0;
}
Compilation message
fountain.cpp: In function 'void dfs(ll, ll)':
fountain.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if((1<<i)>=tren.size()) {lift[i][cvor]=-1; continue;}
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
620 KB |
Output is correct |
| 4 |
Correct |
2 ms |
748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
876 KB |
Output is correct |
| 6 |
Correct |
2 ms |
748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
365 ms |
47456 KB |
Output is correct |
| 2 |
Correct |
420 ms |
44236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
620 KB |
Output is correct |
| 4 |
Correct |
2 ms |
748 KB |
Output is correct |
| 5 |
Correct |
2 ms |
876 KB |
Output is correct |
| 6 |
Correct |
2 ms |
748 KB |
Output is correct |
| 7 |
Correct |
2 ms |
748 KB |
Output is correct |
| 8 |
Correct |
365 ms |
47456 KB |
Output is correct |
| 9 |
Correct |
420 ms |
44236 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
175 ms |
25188 KB |
Output is correct |
| 12 |
Correct |
578 ms |
51296 KB |
Output is correct |
| 13 |
Correct |
403 ms |
45552 KB |
Output is correct |
| 14 |
Correct |
341 ms |
43592 KB |
Output is correct |
| 15 |
Correct |
229 ms |
44004 KB |
Output is correct |
