Submission #236644

#	Time	Username	Problem	Language	Result	Execution time	Memory
236644		kshitij_sodani	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1617 ms	75120 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n;
int it[1000001];
int aa,bb,cc;
int tree[4000001];
int le[1000001];
int ans[1000001];
vector<pair<pair<int,int>,int>> qq[1000001];
void update(int no,int l,int r,int aa,int val){
	if(l==r){
		tree[no]=val;
	}
	else{
		int mid=(l+r)/2;
		if(aa<=mid){
			update(no*2+1,l,mid,aa,val);
		}
		else{
			update(no*2+2,mid+1,r,aa,val);
		}
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		int mid=(l+r)/2;
		return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int m;
	cin>>n>>m;
	stack<int> ss;
	memset(le,0,sizeof(le));

	for(int i=0;i<n;i++){
		cin>>it[i];
		while(ss.size()){
			if(it[ss.top()-1]<=it[i]){
				ss.pop();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			le[i]=ss.top();
		}
		ss.push(i+1);
	}
	for(int i=0;i<m;i++){
		ans[i]=0;
		cin>>aa>>bb>>cc;
		aa-=1;
		bb-=1;
		qq[bb].pb({{aa,cc},i});
	}
	for(int i=0;i<n;i++){
		if(le[i]){
			update(0,0,n-1,le[i]-1,it[le[i]-1]+it[i]);
//			cout<<i<<",,"<<le[i]<<endl;
		}
		for(auto j:qq[i]){
	//		cout<<query(0,0,n-1,j.a.a,i)<<","<<j.b<<endl;
			ans[j.b]=(query(0,0,n-1,j.a.a,i)<=j.a.b?1:0);
		}
	}
	for(int i=0;i<m;i++){
		cout<<ans[i]<<'\n';
	}

	return 0;
}

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