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;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50;
const ll inf=1e16;
vector<array<int,3>>Qs[N];
int res[N],a[N];
int root,nc,lc[2*N],rc[2*N];
ll maks[2*N],lazy[2*N];
void update(int &c,ll x){if(!c)c=++nc;maks[c]+=x;lazy[c]+=x;}
void push(int &c){update(lc[c],lazy[c]),update(rc[c],lazy[c]);lazy[c]=0;}
void Update(int &c,int ss,int se,int qs,int qe,ll x){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return;
if(qs<=ss&&se<=qe){update(c,x);return;}
int mid=ss+se>>1;push(c);
Update(lc[c],ss,mid,qs,qe,x),Update(rc[c],mid+1,se,qs,qe,x);
maks[c]=max(maks[lc[c]],maks[rc[c]]);
}
ll Get(int &c,int ss,int se,int qs,int qe){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return -inf;
if(qs<=ss&&se<=qe)return maks[c];
int mid=ss+se>>1;push(c);
return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
int main(){
int n,q;scanf("%i%i",&n,&q);
for(int i=1;i<=n;i++) scanf("%i",&a[i]);
for(int i=1,l,r,k;i<=q;i++) scanf("%i%i%i",&l,&r,&k),Qs[l].pb({r,k,i});
maks[0]=-inf;
for(int i=1;i<=n;i++) Update(root,1,n,i,i,a[i]);
vector<int>mono={n+1};
for(int i=n;i>=1;i--){
while(mono.size()>1&&a[mono.back()]<=a[i]){
int prosli=mono.back();mono.pop_back();
Update(root,1,n,prosli,mono.back()-1,-a[prosli]);
Update(root,1,n,prosli,prosli,inf);
}
Update(root,1,n,i,mono.back()-1,a[i]);
mono.pb(i);
Update(root,1,n,i,i,-inf);
for(auto j:Qs[i]){
int x=Get(root,1,n,i,j[0]);
//printf("%i %i: %i\n",i,j[0],x);
if(x<=j[1]) res[j[2]]=1;
}
}
for(int i=1;i<=q;i++) printf("%i\n",res[i]);
return 0;
}
Compilation message (stderr)
sortbooks.cpp: In function 'void Update(int&, int, int, int, int, long long int)':
sortbooks.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | int mid=ss+se>>1;push(c);
| ^
sortbooks.cpp: In function 'long long int Get(int&, int, int, int, int)':
sortbooks.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid=ss+se>>1;push(c);
| ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | int n,q;scanf("%i%i",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | for(int i=1;i<=n;i++) scanf("%i",&a[i]);
| ~~~~~^~~~~~~~~~~~
sortbooks.cpp:34:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | for(int i=1,l,r,k;i<=q;i++) scanf("%i%i%i",&l,&r,&k),Qs[l].pb({r,k,i});
| ~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |