Submission #286901

#	Time	Username	Problem	Language	Result	Execution time	Memory
286901		bensonlzl	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1898 ms	100496 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pi;
typedef pair<pi,ll> pii;

ll N, M, L, R, K;
ll W[1000005], hleft[1000005];
ll ans[1000005];

vector<pii> quer[1000005];

ll seg[4000005];

void update(int s, int e, int node, int x, ll v){
	if (s == e){
		seg[node] = max(seg[node],v);
		return;
	}
	if (x <= (s+e)/2) update(s,(s+e)/2,2*node,x,v);
	else update((s+e)/2+1,e,2*node+1,x,v);
	seg[node] = max(seg[2*node],seg[2*node+1]);
}

ll query(int s, int e, int node, int l, int r){
	if (l > e || r < s) return 0;
	if (l <= s && e <= r) return seg[node];
	return max(query(s,(s+e)/2,2*node,l,r),query((s+e)/2+1,e,2*node+1,l,r));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i){
		cin >> W[i];
	}
	vector<pi> st;
	for (int i = 1; i <= N; ++i){
		while (!st.empty() && st.back().first <= W[i]) st.pop_back();
		if (!st.empty()){
			hleft[i] = st.back().second;
		}
		else{
			hleft[i] = -1;
		}
		st.push_back(pi(W[i],i));
	}
	for (int i = 1; i <= M; ++i){
		cin >> L >> R >> K;
		quer[R].push_back(pii(pi(L,K),i));
	}
	for (int i = 1; i <= N; ++i){
		if (hleft[i] != -1){
			update(1,N,1,hleft[i],W[i] + W[hleft[i]]);
		}
		for (auto it : quer[i]){
			ll x = query(1,N,1,it.first.first,i);
			if (x > it.first.second) ans[it.second] = 0;
			else ans[it.second] = 1;
		}
	}
	for (int i = 1; i <= M; ++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