Submission #959842

#	Time	Username	Problem	Language	Result	Execution time	Memory
959842		pcc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3101 ms	261268 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>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

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
	int val[mxn*4];
	int mx[mxn*4];
	vector<int> seg[mxn*4];
	SEG(){}
	void build(int now,int l,int r){
		for(int i = l;i<=r;i++)seg[now].push_back(arr[i]);
		sort(seg[now].begin(),seg[now].end());
		mx[now] = seg[now].back();
		if(l == r)return;
		build(ls,l,mid);
		build(rs,mid+1,r);
		val[now] = max(val[ls],val[rs]);
		if(seg[rs].back()<seg[ls].back())val[now] = max(val[now],seg[ls].back()+seg[rs].back());
		else{
			auto lp = lower_bound(seg[rs].begin(),seg[rs].end(),seg[ls].back());
			if(lp != seg[rs].begin())val[now] = max(val[now],seg[ls].back()+*prev(lp));
		}
		return;
	}
	pii getval(int now,int l,int r,int s,int e,int big = 0){
		if(l>=s&&e>=r){
			pii re;
			re.fs = val[now];
			if(seg[now].back()<big)re.fs = max(re.fs,big+seg[now].back());
			else{
				auto lp = lower_bound(seg[now].begin(),seg[now].end(),big);
				if(lp != seg[now].begin())re.fs = max(re.fs,big+*prev(lp));
			}
			re.sc = max(big,mx[now]);
			return re;
		}
		if(mid>=e)return getval(ls,l,mid,s,e,big);
		else if(mid<s)return getval(rs,mid+1,r,s,e,big);
		else{
			auto re = getval(ls,l,mid,s,e,big);
			auto tmp = getval(rs,mid+1,r,s,e,re.sc);
			return pii(max(re.fs,tmp.fs),max(re.sc,tmp.sc));
		}
	}
#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).fs;
		cout<<(re<=v)<<'\n';
	}
	return 0;
}

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