Submission #1187148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187148		PieArmy	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1279 ms	45668 KiB

sortbooks

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
#define mid ((left+right)>>1)
using namespace std;

struct Seg{
	int n;
	vector<int>tree;
	void init(int N){
		n=N+1;
		tree.resize(n<<2,0);
	}
	int l,r;
	void update(int tar,int val){
		l=tar;
		r=val;
		up();
	}
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return 0;
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	int query(int left,int right){
		l=left;
		r=right;
		return qu();
	}
};

int n,q;
int arr[1000023],las[1000023];
int lef[1000023],rig[1000023],k[1000023],ans[1000023];
int per[1000023];
Seg seg;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>q;
	seg.init(n);
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	vector<int>sta;
	for(int i=1;i<=n;i++){
		while(sta.size()&&arr[sta.back()]<=arr[i])sta.pop_back();
		if(sta.size()){
			las[i]=sta.back();
		}
		sta.pb(i);
	}
	for(int i=1;i<=q;i++){
		cin>>lef[i]>>rig[i]>>k[i];
	}
	iota(per,per+q,1);
	sort(per,per+q,[&](const int &x,const int &y){
		return rig[x]<rig[y];
	});
	int itr=0;
	for(int j=0;j<q;j++){
		while(itr<rig[per[j]]){
			itr++;
			seg.update(las[itr],arr[las[itr]]+arr[itr]);
		}
		ans[per[j]]=(seg.query(lef[per[j]],rig[per[j]])<=k[per[j]]);
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
}

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