Submission #959800

#	Time	Username	Problem	Language	Result	Execution time	Memory
959800		pcc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	912 ms	69960 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e6+10;
int arr[mxn];
int N,Q;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	struct node{
		int mx,mn;
		int val;
		node(){mx = 0,mn = 2e9,val = 0;}
	};
	node seg[mxn*4];
	SEG(){
		for(auto &i:seg)i = node();
	}
	node pull(node a,node b){
		node re;
		re.mx = max(a.mx,b.mx);
		re.mn = min(a.mn,b.mn);
		re.val = max({a.val,b.val,a.mx-b.mn});
		return re;
	}
	void build(int now,int l,int r){
		if(l == r){
			seg[now].mx = seg[now].mn = arr[l];
			seg[now].val = 0;
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	node getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs 
#undef mid
};

SEG seg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	seg.build(0,1,N);
	while(Q--){
		int s,e,v;
		cin>>s>>e>>v;
		int re = seg.getval(0,1,N,s,e).val;
		cout<<(re<=v)<<'\n';
	}
	return 0;
}

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