Submission #502117

#	Time	Username	Problem	Language	Result	Execution time	Memory
502117		Mr_Husanboy	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1405 ms	76436 KiB

sortbooks

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const double PI=3.1415926535897932384626433832795;
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;

const int N=1e6+5;

int tree[4*N];

void update(int x,int l,int r, int pos, int val){
	if(l==r){
		tree[x]=max(tree[x],val);
		return;	
	}
	int m=(l+r)/2;
	if(pos<=m){
		update(2*x,l,m,pos,val);
	}else
	update(2*x+1,m+1,r,pos,val); 
	tree[x]=max(tree[x*2],tree[x*2+1]);
	return;
}

int get(int x,int l,int r, int ll, int rr){
	if(r<ll||l>rr){
		return 0;
	}
	if(r<=rr&&l>=ll){
		return tree[x];
	}
	int m=(l+r)/2;
	return max(get(x*2,l,m,ll,rr),get(2*x+1,m+1,r,ll,rr));
}

vector<pair<int,pair<int,int>>> v[N];

int main(){
	ios;
	int n,q; cin>>n>>q;
	int a[n+1];for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=q;i++){
		int l,r,k; cin>>l>>r>>k;
		v[r].push_back({l,make_pair(i,k)});
	}
	vector<int> ans(::N,0); stack<int> s;
	a[0]=2e9;
	s.push(0);
	for(int i=1;i<=n;i++){
		while(a[s.top()]<=a[i]) s.pop();
		int j=s.top();
		if(j!=0){
			update(1,1,n,j,a[j]+a[i]);
		}
		for(auto u:v[i]){
			ans[u.second.first]=(get(1,1,n,u.first,i)<=u.second.second?1:0);
		}
		s.push(i);
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
}

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