제출 #312763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312763		mosiashvililuka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	2821 ms	95508 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
const int N=2200009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,t,tes,za,f[1000009],seg[N],seg2[N],seg3[N],z,l,r,pas1,pas2,mx,mx2,ar[1000009];
vector <pair <int, int> > vv[N];
void up(int q){
	if(q==0) return;
	if(seg[q*2]>=seg[q*2+1]){
		seg[q]=seg[q*2];
		seg2[q]=seg2[q*2];
		seg3[q]=seg3[q*2];
	}else{
		seg[q]=seg[q*2+1];
		seg2[q]=seg2[q*2+1];
		seg3[q]=seg3[q*2+1];
	}
	//cout<<q<<" l "<<vv[q*2].size()<<" "<<vv[q*2+1].size()<<endl;
	if(vv[q*2].size()==0||vv[q*2+1].size()==0){
		up(q/2);
		return;
	}
	vector <pair <int, int> >::iterator it;
	int qw=vv[q*2][vv[q*2].size()-1].first,we=vv[q*2][vv[q*2].size()-1].second;
	it=lower_bound(vv[q*2+1].begin(),vv[q*2+1].end(),make_pair(qw,0));
	//cout<<q<<" kkk1 "<<qw<<" "<<(*it).first<<endl;
	if(vv[q*2+1].begin()==it){
		up(q/2);
		return;
	}
	it--;
	//cout<<q<<" kkk2 "<<qw<<" "<<(*it).first<<endl;
	if(seg[q]<qw+(*it).first){
		seg[q]=qw+(*it).first;
		seg2[q]=we;
		seg3[q]=(*it).second;
	}
	up(q/2);
}
void read(int q, int w, int rr){
	if(r<q||l>w) return;
	if(q>=l&&w<=r){
		vector <pair <int, int> >::iterator it;
		//cout<<"rr "<<q<<endl;
		if(vv[rr].size()==0) return;
		if(z<seg[rr]){
			z=seg[rr];
			pas1=seg2[rr];
			pas2=seg3[rr];
		}
		it=lower_bound(vv[rr].begin(),vv[rr].end(),make_pair(mx,0));
		if(it!=vv[rr].begin()){
			it--;
			if(z<mx+(*it).first){
				z=mx+(*it).first;
				pas1=mx2;
				pas2=(*it).second;
			}
		}
		int qw=vv[rr][vv[rr].size()-1].first,we=vv[rr][vv[rr].size()-1].second;
		if(mx<qw){
			mx=qw;
			mx2=we;
		}
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	if(a>200000){
		for(i=a; i>=1; i--){
			if(f[i+1]>=f[i]){
				ar[i]=ar[i+1];
			}else{
				ar[i]=i;
			}
		}
		for(t=1; t<=tes; t++){
			cin>>c>>d>>e;
			if(ar[c]>=d){
				cout<<1<<endl;
			}else{
				cout<<0<<endl;
			}
		}
		return 0;
	}
	za=1;
	while(za<a) za*=2;
	for(i=1; i<=a; i++){
		zx=(i+za-1);
		while(zx>0){
			vv[zx].push_back(make_pair(f[i],i));
			zx/=2;
		}
	}
	for(i=1; i<=za*2; i++){
		sort(vv[i].begin(),vv[i].end());
	}
	for(i=1; i<=a; i++){
		up((i+za-1)/2);
	}
	//cout<<seg[1]<<" k "<<seg2[1]<<" "<<seg3[1]<<endl;
	//cout<<seg[2]<<" k2 "<<seg2[2]<<" "<<seg3[2]<<endl;
	for(t=1; t<=tes; t++){
		cin>>c>>d>>e;
		z=0;pas1=0;pas2=0;mx=0;mx2=0;
		l=c;r=d;
		read(1,za,1);
		if(z<=e){
			cout<<1<<endl;
		}else{
			cout<<0<<endl;
		}
	}
	return 0;
}

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