Submission #932947

#	Time	Username	Problem	Language	Result	Execution time	Memory
932947		beepbeepsheep	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1360 ms	114804 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=1e6+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

stack<ll> s;
ll arr[maxn];
ll nxt[maxn];
struct node{
	ll n;
	node(ll _n):n(_n){}
	ii tree[maxn*2];
	void upd(int i, int x){
		int ori=i;
	    i += n;
	    tree[i] = {x,ori};
	    i >>= 1;
	    while(i > 0){
	        tree[i] = max(tree[i<<1], tree[i<<1|1]);
	        i>>=1;
	    }
	}
	ii query(int l, int r){ ///[l, r] both inclusive
	    ii ans = {0,0};
	    for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
	        if(l&1){
	            ans = max(ans, tree[l]);
	            l++;
	        }
	        if(r&1){
	            r--;
	            ans = max(ans, tree[r]);
	        }
	    }
	    return ans;
	}
}*val,*root;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,q;
	cin>>n>>q;
	val=new node(n);
	root=new node(n);
	for (int i=1;i<=n;i++){
		cin>>arr[i];
		while (s.size() && arr[s.top()]<=arr[i]){
			nxt[s.top()]=i;
			s.pop();
		}
		s.emplace(i);
		val->upd(i,arr[i]);
	}
	while (s.size()){
		nxt[s.top()]=n+1;
		s.pop();
	}
	for (int i=1;i<=n;i++){
		if (nxt[i]-1!=i){
			ll ele=val->query(i+1,nxt[i]-1).first;
			root->upd(i,arr[i]+ele);
		}
	}
	ll l,r,x;
	for (int i=1;i<=q;i++){
		cin>>l>>r>>x;
		ll p=val->query(l,r).second;
		cerr<<p<<' ';
		ll ans=0;
		if (l!=p){
			ans=max(ans,root->query(l,p-1).first);
		}
		if (p!=r){
			ans=max(ans,arr[p]+val->query(p+1,r).first);
		}
		cout<<(ans<=x)<<endl;
		cerr<<ans<<endl;
	}
	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