Submission #501670

#	Time	Username	Problem	Language	Result	Execution time	Memory
501670		BY_KUTBILIM	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2255 ms	87840 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
int n, m, w[1000001], a[5000001], l[1000001], pos, val, x, y;
bool f[1000001];

struct Query {int id, l, k; };
vector<Query> q[1000001];

stack<int> s;

void update(int nod, int l, int r){
	if(l == r)a[nod] = max(a[nod], val);
	else{
		int m = (l + r) / 2;
		if(pos <= m)update(2*nod, l, m);
		else update(2*nod+1,m+1, r);
		a[nod] = max(a[2*nod], a[2*nod+1]);
	}
}
int query(int nod, int l, int r){
	if(x <= l and r <= y)return a[nod];
	int m = (l + r) / 2, res = 0;
	if(x <= m)res = max(res, query(2*nod,l, m));
	if(m < y)res = max(res, query(2*nod+1,m+1,r));
	return res;
}
void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> w[i];
	}
	for(int i = 1, r, l, k; i <= m; i++){
		cin >> l >> r >> k;
		q[r].push_back({i, l, k});
	}
	for(int i = 1; i <= n; i++){
		l[i] = i;
		for(; !s.empty() && w[i] >= w[s.top()]; s.pop())
			l[i] = l[s.top()];
		s.push(i);
	}
	for(int i = 1; i <= n; i++){
		if(l[i] > 1){
			pos = l[i] - 1;
			val = w[i] + w[pos];
			update(1, 1, n);
		}
		for(auto j : q[i]){
			x = j.l, y = i;
			f[j.id] = (j.k >= query(1, 1, n));
		}
	}
	for(int i = 1; i <= m; i++){
		cout << f[i] << '\n';
	}
}

int main(){
	solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23