Submission #479034

#	Time	Username	Problem	Language	Result	Execution time	Memory
479034		Christopher_	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	8 / 100	3066 ms	19848 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct node {
	int mx;
};

vector<node> tree;
vector<int> a;

void Build(int x, int l, int r) {
	if (l == r) {
		tree[x].mx = a[l];
		return;
	}
	int m = (l + r) >> 1;
	Build((x << 1) + 1, l, m);
	Build((x << 1) + 2, m + 1, r);
	tree[x].mx = max(tree[(x << 1) + 1].mx, tree[(x << 1) + 2].mx);
}

void Build() {
	int n = (int) a.size();
	tree.resize(4 * n + 1);
	Build(0, 0, n - 1);
}

int Find(int x, int l, int r, int ll, int rr, int val) {
	if (rr < l || ll > r) return 0;
	else if (ll >= l && rr <= r && tree[x].mx < val) return tree[x].mx;
	else if (ll >= l && rr <= r && ll == rr) return 0;
	int m = (ll + rr) >> 1;
	int left = Find((x << 1) + 1, l, r, ll, m, val);
	int right = Find((x << 1) + 2, l, r, m + 1, rr, val);
	return max(left, right);
}

int Find(int l, int r, int x) {
	int n = (int) a.size();
	return Find(0, l, r, 0, n - 1, x);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	a.resize(n);
	for (int &e : a) {
		cin >> e;
	}
	Build();
	while (q--) {
		bool ok = true;
		int l, r, c;
		cin >> l >> r >> c;
		--l, --r;
		for (int i = l; i < r; ++i) {
			if (a[i] > a[i + 1]) {
				int x = Find(i + 1, r, a[i]);
				//cout << "x" << x << '\n';
				if (x + a[i] > c) {
					cout << 0 << '\n';
					ok = false;
					break;
				}
			}
		}
		if (ok) cout << 1 << '\n';
	}
}

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