Submission #286892

#	Time	Username	Problem	Language	Result	Execution time	Memory
286892		dvdg6566	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3084 ms	206376 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
const int MAXN=1001000;
const ll MOD=998244353;

int A[MAXN];
int N,Q,a,b,c;

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;v=A[s];
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=min(l->v,r->v);
		}
	}
	int ask(int a,int b){
		if(a==s&&e==b)return v;
		if(b<=m)return l->ask(a,b);
		if(a>m)return r->ask(a,b);
		return min(l->ask(a,m),r->ask(m+1,b));
	}
}*maxes,*mins;

int fs[MAXN];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>Q;
	for(int i=1;i<=N;++i){
		cin>>A[i];
		A[i]=-A[i];
	}
	maxes=new node(1,N);
	for(int i=1;i<=N;++i){
		A[i]=abs(A[i]);
	}
	mins=new node(1,N);
	vpi V;
	V.pb(1,1);
	for(int i=2;i<=N;++i){
		if(A[i]>=A[V.back().s])++V.back().s;
		else V.pb(i,i);
	}

	for(auto i:V){
		for(int k=i.f;k<=i.s;++k)fs[k]=i.f;
	}

	while(Q--){
		cin>>a>>b>>c;
		int sf=fs[b]-1;

		if(sf < a){
			cout<<"1\n";
			continue;
		}

		// cout<<a<<' '<<sf<<'\n';
		if(mins->ask(a,b) + abs(maxes->ask(a,sf)) > c){
			cout<<"0\n";
		}else cout<<"1\n";
	}
}

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