Submission #998417

#	Time	Username	Problem	Language	Result	Execution time	Memory
998417		amirhoseinfar1385	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3043 ms	55140 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int all[maxn],n,q,kaf=(1<<20);

struct segment{
	pair<int,int>seg[(1<<21)];
	void ins(int i,pair<int,int>w){
		i+=kaf;
		while(i>0){
			seg[i]=max(seg[i],w);
			i>>=1;
		}
	}
	pair<int,int>pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(0,0);
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

void vorod(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
}

void pre(){
	for(int i=1;i<=n;i++){
		seg.ins(i,make_pair(all[i],i));
	}
}

int calc(int l,int r,int w){
	if(l>r){
		return 1;
	}
	pair<int,int>p=seg.pors(1,0,kaf-1,l,r);
	if(p.second==r){
		return calc(l,r-1,w);
	}
	pair<int,int>pp=seg.pors(1,0,kaf-1,p.second+1,r);
	if(p.first+pp.first>w){
		return 0;
	}
	return (calc(l,p.second-1,w)&calc(p.second+1,r,w));
}

void solve(){
	for(int i=0;i<q;i++){
		int l,r,w;
		cin>>l>>r>>w;
		cout<<calc(l,r,w)<<endl;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	vorod();
	pre();
	solve();
}

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