Submission #910536

#	Time	Username	Problem	Language	Result	Execution time	Memory
910536		daoquanglinh2007	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	835 ms	93688 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e6;

int N, M, w[NM+5], pre[NM+5];
vector <int> st;
int bit[NM+5];
vector <pair <pii, int> > q[NM+5];
bool ans[NM+5];

void update(int x, int val){
	while (x <= N){
		bit[x] = max(bit[x], val);
		x += x & (-x);
	}
}

int get(int x){
	int res = 0;
	while (x > 0){
		res = max(res, bit[x]);
		x -= x & (-x);
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++){
		cin >> w[i];
		while (!st.empty() && w[st.back()] <= w[i]) st.pop_back();
		if (!st.empty()){
			pre[i] = st.back();
		}
		st.push_back(i);
	}
	for (int i = 1; i <= M; i++){
		int l, r, k; cin >> l >> r >> k;
		q[r].push_back(mp(mp(l, k), i));
	}
	for (int i = 1; i <= N; i++){
		if (pre[i] > 0) update(N-pre[i]+1, w[i]+w[pre[i]]);
		for (pair <pii, int> P : q[i]){
			ans[P.se] = get(N-P.fi.fi+1) <= P.fi.se;
		}
	}
	for (int i = 1; i <= M; i++) cout << ans[i] << '\n';
	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