Submission #98165

#TimeUsernameProblemLanguageResultExecution timeMemory
98165314rateCambridge (info1cup18_cambridge)C++14
55 / 100
2090 ms15468 KiB
#include <bits/stdc++.h> using namespace std; struct RMQ_MAX { vector<vector<int>>ret; vector<int>mylog; void build(int n,int a[]) { ret.resize(n+1); mylog.resize(n+1); for(int i=2;i<=n;i++) { mylog[i]=1+mylog[i/2]; } for(int i=1;i<=n;i++) { ret[i].resize(mylog[n]+1,-(1<<30)); ret[i][0]=a[i]; } for(int k=1;(1<<k)<=n;k++) { for(int i=1;i+(1<<k)-1<=n;i++) { ret[i][k]=max(ret[i][k-1],ret[i+(1<<(k-1))][k-1]); } } } int gt(int l,int r) { int k=mylog[r-l+1]; return max(ret[l][k],ret[r-(1<<k)+1][k]); } }; RMQ_MAX rm; typedef long long ll; const int N=(int)1e5+7; int n,m; int a[N]; int b[N]; ll ps[N]; ll gt(int l,int r) { return ps[r]-ps[l-1]; } struct info { int a; int b; }; bool cmp(info x,info y) { return x.b<y.b; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; ps[i]=ps[i-1]+a[i]; } rm.build(n,b); while(m--) { int l,r; cin>>l>>r; ll tots=gt(l,r); int big=rm.gt(l,r); /// cout<<":"<<tots<<" , "<<big<<"\n"; if(tots>=(ll)big) { cout<<"0\n"; continue; } vector<info>keks; for(int i=l;i<=r;i++) { keks.push_back({a[i],b[i]}); } sort(keks.begin(),keks.end(),cmp); int tos=0; bool ok=1; for(auto &it:keks) { tos+=it.a; if(tos>=it.b) { ok=0; break; } } cout<<(int)ok<<"\n"; /// cout<<"?\n"; } } /** 4 3 1 10 14 18 2 7 10 12 3 4 2 4 1 3 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...