Submission #576482

#TimeUsernameProblemLanguageResultExecution timeMemory
576482MrM7mdFountain (eJOI20_fountain)C++17
60 / 100
72 ms3228 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" const int MOD = 1e9 + 7; pair<int,int> a[10000000]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,q; cin >> n>>q; int pref[n+1]={0}; for(int i=0;i<n;i++){ cin >> a[i].first>>a[i].second; pref[i+1]=a[i].second; pref[i+1]+=pref[i]; } pref[n]=a[n-1].second; pref[n]+=pref[n-1]; a[n]={INT_MAX,INT_MAX}; if(n<=1000&&q<=2000){ while(q--){ int r,v; cin >>r >> v; int cur=a[r-1].first; v-=a[r-1].second; int ans=r-1; for(int i=r;i<=n;i++){ if(a[i].first>cur){ if(v<=0) { break; } ans=i; cur=a[i].first; v-=a[i].second; } } if(ans==n)ans=-1; cout<<ans+1<<endl; } } else{ while(q--){ int r,v; cin >>r >> v; v+=pref[r-1]; int ans=lower_bound(pref,pref+n,v)-pref; if(v>pref[ans+1])ans++; if(ans==n)ans=0; cout<<ans<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...