This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+4;
vector<int>st[4*N];
int mx[4*N],a[N],cur,ans,n,q;
void build(int node=1,int tl=0,int tr=n-1){
if(tl==tr){
mx[node]=0;
st[node]={a[tr]};
return;
}
int mid=(tl+tr)/2;
build(node*2,tl,mid);
build(node*2+1,mid+1,tr);
st[node].resize((int)st[node*2].size()+(int)st[node*2+1].size());
merge(st[node*2].begin(),st[node*2].end(),st[node*2+1].begin(),st[node*2+1].end(),st[node].begin());
mx[node]=max(mx[node*2],mx[node*2+1]);
int levi=st[node*2].back();
auto it=upper_bound(st[node*2+1].begin(),st[node*2+1].end(),levi-1);
if(it!=st[node*2+1].begin())
it=prev(it);
if(*it<levi)
mx[node]=max(mx[node],*it+levi);
}
void qry(int l,int r,int node=1,int tl=0,int tr=n-1){
if(tl>=l&&tr<=r){
ans=max(ans,mx[node]);
assert(st[node].size());
auto it=upper_bound(st[node].begin(),st[node].end(),cur-1);
if(it!=st[node].begin())
it=prev(it);
if(*it<cur)
ans=max(ans,*it+cur);
cur=max(cur,st[node].back());
return;
}
int mid=(tl+tr)/2;
if(mid>=l)qry(l,r,2*node,tl,mid);
if(mid<=r-1)qry(l,r,2*node+1,mid+1,tr);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
for(int i=0;i<n;++i)
cin>>a[i];
build();
while(q--){
int l,r,k;
cin>>l>>r>>k;
--l,--r;
cur=0,ans=0;
qry(l,r);
cout<<(ans<=k)<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |