Submission #286896

#	Time	Username	Problem	Language	Result	Execution time	Memory
286896		bensonlzl	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1793 ms	67732 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

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

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

vector<pii> quer[1000005];

int seg[4000005];

void update(int s, int e, int node, int x, int 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]);
}

int query(int s, int e, int node, int l, int r){
	if (l > e || r < s) return -1;
	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]){
			int 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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23