제출 #998427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998427		amirhoseinfar1385	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1288 ms	75208 KiB

sortbooks

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

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,sega;

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));
	}
	vector<int>v;
	for(int i=n;i>=1;i--){
		while((int)v.size()>0&&all[i]>all[v.back()]){
			v.pop_back();
		}
		if((int)v.size()>0){
			tr[i]=v.back();
		}else{
			tr[i]=n+1;
		}
		v.push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(tr[i]==i+1){
			continue;
		}
		sega.ins(i,make_pair(all[i]+seg.pors(1,0,kaf-1,i+1,tr[i]-1).first,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){
		pair<int,int>pp=seg.pors(1,0,kaf-1,p.second+1,r);
		if(p.first+pp.first>w){
			return 0;
		}
	}
	if(p.second==l){
		return 1;
	}
	return sega.pors(1,0,kaf-1,l,p.second-1).first<=w;
}

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

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: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23