Submission #154102

#	Time	Username	Problem	Language	Result	Execution time	Memory
154102		beso123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3073 ms	163460 KiB

sortbooks

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int mas[4000001];
int T[1000001];
int mx[1000001];
int mn[1000001];
int R[1000001];
vector <int> v[4000001];
void buildM (int p,int tl,int tr){
	if (tl==tr){
		mn[p]=R[tl];
		return ;
	}
	int mid=tl+tr>>1;
	buildM(p+p,tl,mid);
	buildM(p+p+1,mid+1,tr);
	
	mn[p]=min(mn[2*p],mn[2*p+1]);
}
int findM (int p,int tl,int tr,int l,int r){
	if(l>r) return 0;
	if (l<=tl&&tr<=r){
		return mn[p];
	}
	
	if (tl>r||l>tr){
		return 0;
	}
	
	int mid= tl+tr>>1;
	int a=findM(p+p,tl,mid,l,r);
	int b=findM(p+p+1,mid+1,tr,l,r);
	return min(a,b);
}
void build (int p,int tl,int tr){
	if (tl==tr){
		v[p].push_back(mas[tl]);
		mx[p]=mas[tl];
		T[p]=0;
		return ;
	}
	int mid=tl+tr>>1;
	build(p+p,tl,mid);
	build(p+p+1,mid+1,tr);
	
	int e=0,i=0;
	while (e<v[2*p+1].size()||i<v[2*p].size()){
		if (e==v[2*p+1].size()){
			v[p].push_back(v[2*p][i]);
			i++;
			continue;
		}
		if (i==v[2*p].size()){
			v[p].push_back(v[2*p+1][e]);
			e++;
			continue;
		}
		if (v[2*p+1][e]<v[2*p][i]){
			v[p].push_back(v[2*p+1][e]);
			e++;
		}
		else{
			v[p].push_back(v[2*p][i]);
			i++;
		}
	}
	//cout<<p<<" "<<v[p].size()<<endl;
	int MAX=0;
	for (int i=tl;i<=tr;i++){
		if (mas[i]<MAX){
			T[p]=max(T[p],MAX+mas[i]);
		}
		MAX=max(mas[i],MAX);
	}
	
	mx[p]=max(mx[2*p],mx[2*p+1]);
}
int CURMAX=0;
int find (int p,int tl,int tr,int l,int r){
	if (l<=tl&&tr<=r){
		int beg=0,en=v[p].size()-1,as=-1;
		while (beg<=en){
			int mid=(beg+en>>1);
			if(v[p][mid]>=CURMAX){
				en=mid-1;
			}
			else{
				beg=mid+1;
				as=mid;
			}
		}
		int ke;
		int e=CURMAX;
		CURMAX=max(CURMAX,mx[p]);
		if (as==-1) return T[p]; 
			else ke=max(T[p],e+v[p][as]);
		return ke;
	}
	
	if (tl>r||l>tr){
		return 0;
	}
	
	int mid= tl+tr>>1;
	int a=find(p+p,tl,mid,l,r);
	int b=find(p+p+1,mid+1,tr,l,r);
	return max(a,b);
}
int t;
int l[1000001],r[1000001],x[1000001];
set <pair <int,int> > s;
main (){
	ios_base::sync_with_stdio(false);
	cin>>n>>t;
	int MIN=1000000000000;
	for (int i=1;i<=n;i++){
		cin>>mas[i];
		MIN=min(MIN,mas[i]);
	}
	
	bool ok=true;
	for (int i=1;i<=t;i++){
		cin>>l[i]>>r[i]>>x[i];
		CURMAX=0;
		if (x[i]>MIN){
			ok=false;
		}
	}
	
	if (ok){
		for (int i=1;i<=n;i++){
			if(mas[i]>mas[i+1]){
				R[i+1]=-1;
			}
		}
		buildM(1,1,n);
		for (int i=1;i<=t;i++){
			CURMAX=0;
			int wow=findM (1,1,n,l[i]+1,r[i]);
			cout<<(wow!=-1)<<endl;
		}
	}
	else{
		
		build (1,1,n);
		for (int i=1;i<=t;i++){
			CURMAX=0;
			int wow=find (1,1,n,l[i],r[i]);
			cout<<(wow<=x[i])<<endl;
		}
	}
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void buildM(long long int, long long int, long long int)':
sortbooks.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp: In function 'long long int findM(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= tl+tr>>1;
           ~~^~~
sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp:49:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (e<v[2*p+1].size()||i<v[2*p].size()){
         ~^~~~~~~~~~~~~~~~
sortbooks.cpp:49:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (e<v[2*p+1].size()||i<v[2*p].size()){
                            ~^~~~~~~~~~~~~~
sortbooks.cpp:50:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (e==v[2*p+1].size()){
       ~^~~~~~~~~~~~~~~~~
sortbooks.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i==v[2*p].size()){
       ~^~~~~~~~~~~~~~~
sortbooks.cpp: In function 'long long int find(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:85:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=(beg+en>>1);
             ~~~^~~
sortbooks.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= tl+tr>>1;
           ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:114:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main (){
       ^

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