Submission #651246

#	Time	Username	Problem	Language	Result	Execution time	Memory
651246		peter940324	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	136 ms	16652 KiB

sortbooks

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

#define int long long
#define double long double
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define pii pair<int,int>
#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define pf push_front
#define all(x) x.begin(),x.end()

#define de(x) cout << #x << ' ' << x << '\n';
template<class T> void prt(T l,T r){
  while(l!=r) cout << *l << ' ',l++;
  cout << '\n';
}

const int N=2e5+5,M=1e9+7,INF=1e18;

struct qr{
	int l,r,ind,x,ans;
};

int mx[4*N]{0},add[4*N]{0},ans[4*N]{0};
int a[N];
void build(int l,int r,int cur){
	if(r-l<=1) return mx[cur]=a[l],void();
	int mid=(l+r)/2;
	build(l,mid,cur*2);
	build(mid,r,cur*2+1);
	mx[cur]=max(mx[cur*2],mx[cur*2+1]);
}
void put_tag(int cur,int x){
	if(x>add[cur]&&x<mx[cur]){
		add[cur]=x;
		ans[cur]=max(ans[cur],mx[cur]+add[cur]);
	}
}
void push(int cur){
	put_tag(cur*2,add[cur]);
	put_tag(cur*2+1,add[cur]);
}
void upd(int l,int r,int cur,int ql,int qr,int x){
	if(ql>=r||qr<=l) return;
	if(ql<=l&&r<=qr) return put_tag(cur,x),void();
	int mid=(l+r)/2;
	push(cur);
	upd(l,mid,cur*2,ql,qr,x);
	upd(mid,r,cur*2+1,ql,qr,x);
	ans[cur]=max({ans[cur*2],ans[cur*2+1],mx[cur]+add[cur]});
}
int qry(int l,int r,int cur,int ql,int qr){
	if(ql>=r||qr<=l) return 0;
	if(ql<=l&&qr>=r) return ans[cur];
	int mid=(l+r)/2;
	push(cur);
	return max(qry(l,mid,cur*2,ql,qr),qry(mid,r,cur*2+1,ql,qr));
}

signed main(){
  IO
	int n,q;cin >> n >> q;
	for(int i=1;i<=n;i++) cin >> a[i];
	build(1,n+1,1);
	vector<qr> Q(q);
	for(int i=0;i<q;i++){
		cin >> Q[i].l >> Q[i].r >> Q[i].x;
		Q[i].ind=i;
	}
	sort(all(Q),[](qr aa,qr bb){
		return aa.r<bb.r;
	});
	int ind=1;
	for(int i=0;i<q;i++){
		while(ind<=Q[i].r){
			upd(1,n+1,1,1,ind+1,a[ind]);
			ind++;
		}
		int x=qry(1,n+1,1,Q[i].l,Q[i].r+1);
		if(x>Q[i].x) Q[i].ans=0;
		else Q[i].ans=1;
	}
	sort(all(Q),[](qr aa,qr bb){
		return aa.ind<bb.ind;
	});
	for(int i=0;i<q;i++) cout << Q[i].ans << '\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