Submission #286882

#	Time	Username	Problem	Language	Result	Execution time	Memory
286882		oolimry	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2914 ms	158308 KiB

sortbooks

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

struct node{
	int s, e, m;
	int val = 0, lazy = 0;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void apply(int L){
		lazy += L;
		val += L;
	}
	
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
	
	void update(int S, int E, int L){
		push();
		if(S == s && e == E){
			apply(L);
			return;
		}
		else if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else{
			update(S,m,L);
			update(m+1,E,L);			
		}
		val = max(l->val, r->val);
	}
	
	int query(int S, int E){
		push();
		if(S == s && e == E) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return max(l->query(S, m), r->query(m+1, E));	
	}
	
} *root;

int arr[1000005];
int ans[1000005];
struct query{ int r, K, id; };
vector<query> queries[1000005];

void update(int S, int E, int L){
	if(S > E) return;
	//cout << S << " " << E << " " << L << "U\n";
	root->update(S, E, L);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	root = new node(1, n);
	
	for(int i = 1;i <= n;i++){
		cin >> arr[i];
	}
	
	for(int q = 0;q < Q;q++){
		int l, r, K; cin >> l >> r >> K;
		queries[l].push_back({r, K, q});
	}
	
	arr[n+1] = 1023456789;
	vector<int> S;
	S.push_back(n+1);
	
	for(int l = n;l >= 1;l--){
		
		//cout << l << " " << arr[l] << ":\n";
		
		while(true){
			int T = S.back();
			if(arr[T] >= arr[l]) break;
			
			///do something else here
			S.pop_back();
			int nxt = S.back();
			update(T+1, nxt-1, -arr[T]);
			update(T, T, arr[T]);
		}
		
		update(l+1, S.back()-1, arr[l]);
		S.push_back(l);
		//for(int i = sz(S)-1;i>=0;i--) cout << S[i] << " ";
		//cout << "\n";
		
		for(query q : queries[l]){
			int res = root->query(l, q.r);
			ans[q.id] = (res <= q.K);
		}
	}
	
	for(int q = 0;q < Q;q++) cout << ans[q] << '\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