Submission #1113265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113265		StefanSebez	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2712 ms	152504 KiB

sortbooks

#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=1e17;
vector<array<ll,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(ll i=1,l,r,k;i<=q;i++) scanf("%lld%lld%lld",&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]);
		Update(root,1,n,i,i,-inf);
		mono.pb(i);
		for(auto j:Qs[i]){
			ll 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:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for(ll i=1,l,r,k;i<=q;i++) scanf("%lld%lld%lld",&l,&r,&k),Qs[l].pb({r,k,i});
      |                                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23