Submission #172631

#TimeUsernameProblemLanguageResultExecution timeMemory
172631LinusTorvaldsFanHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
17 / 100
3017 ms19160 KiB
#include <bits/stdc++.h> using namespace std; const int maxn=100000+7; int w[maxn]; const int K=330; int block_answer[maxn]; int block_max[maxn]; const int Q=1<<17; vector<int> tree[2*Q]; void build(int n) { for(int i=Q;i<Q+n;i++){ tree[i].push_back(w[i-Q]); } for(int i=Q-1;i>0;i--){ std::merge(tree[2*i].begin(),tree[2*i].end(),tree[2*i+1].begin(),tree[2*i+1].end(),std::back_inserter(tree[i])); } } int get(int l, int r, int x) { int ans=-1; for(l+=Q,r+=Q;l<r;l>>=1,r>>=1){ if(l&1) { auto t=lower_bound(tree[l].begin(),tree[l].end(),x); if(t!=tree[l].begin()){ t--; ans=max(ans,*t); } l++; } if(r&1) { r--; auto t=lower_bound(tree[r].begin(),tree[r].end(),x); if(t!=tree[r].begin()){ t--; ans=max(ans,*t); } } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("input.txt","r",stdin); int n,m; cin>>n>>m; for(int i=0;i<n;i++)cin>>w[i]; for(int i=0;i+K-1<n;i+=K){ int block=i/K; block_answer[block]=-1; for(int l=i;l<i+K;l++){ for(int r=l+1;r<i+K;r++){ if(w[l]>w[r]){ block_answer[block]=max(block_answer[block],w[l]+w[r]); } } } for(int l=i;l<i+K;l++){ block_max[block]=max(block_max[block],w[l]); } //cout<<block_answer[block]<<" "; //cout<<block_max[block]<<endl; } build(n); for(;m;m--){ int l,r,k; cin>>l>>r>>k; l--; r--; int ans=-1; for(;l%K!=0 && l <= r;l++){ int q=get(l+1,r+1,w[l]); //cout<<q<<endl; if(q!=-1) ans=max(ans,w[l]+q); } for(;l+K-1<=r;l+=K){ int block=l/K; ans=max(ans,block_answer[block]); int q=get(l+K,r+1,block_max[block]); // cout<<":"<<q<<"\n"; if(q!=-1) ans=max(ans,block_max[block]+q); } for(;l<=r;l++){ int q=get(l+1,r+1,w[l]); // cout<<q<<endl; if(q!=-1) ans=max(ans,w[l]+q); } // cout<<ans<<endl; if(ans<=k){ cout<<1<<'\n'; } else { cout<<0<<'\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...