Submission #172600

#	Time	Username	Problem	Language	Result	Execution time	Memory
172600		LinusTorvaldsFan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3060 ms	50028 KiB

sortbooks

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1000000 + 7;

int w[maxn];

const int K = 400;

int block_answer[maxn];
int block_max[maxn];

const int Q = 1 << 18;
vector<int> tree[2 * Q];

void build(int n) {
	for (int i = Q; i < Q + n; i++) {
		tree[i].push_back(w[i - Q]);
	}
	for (int i = Q - 1; i > 0; i--) {
		std::merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), std::back_inserter(tree[i]));
	}
}

int get(int l, int r, int x) {
	int ans = -1;
	for (l += Q, r += Q; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			auto t = lower_bound(tree[l].begin(), tree[l].end(), x);
			if (t != tree[l].begin()) {
				t--;
				ans = max(ans, *t);
			}
		}
		if (r & 1) {
			r--;
			auto t = lower_bound(tree[r].begin(), tree[r].end(), x);
			if (t != tree[r].begin()) {
				t--;
				ans = max(ans, *t);
			}
		}
	}
	return ans;
}

int main() {
	// freopen("input.txt","r",stdin);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> w[i];

	for (int i = 0; i + K - 1 < n; i += K) {
		int block = i / K;
		block_answer[block] = -1;
		for (int l = i; l < i + K; l++) {
			for (int r = l + 1; r < i + K; r++) {
				if (w[l] > w[r]) {
					block_answer[block] = max(block_answer[block], w[l] + w[r]);
				}
			}
		}

		for (int l = i; l < i + K; l++) {
			block_max[block] = max(block_max[block], w[l]);
		}
		// cout<<block_answer[block]<<" ";
	}

	build(n);

	for (; m; m--) {
		int l, r, k;
		cin >> l >> r >> k;
		l--; r--;
		int ans = -1;

		for (; l % K != 0 && l <= r; l++) {
			int q = get(l + 1, r + 1, w[l]);
			if (q != -1) ans = max(ans, w[l] + q);
		}

		for (; l + K - 1 <= r; l += K) {
			int block = l / K;
			ans = max(ans, block_answer[block]);
			int q = get(l + K, r + 1, block_max[block]);
			if (q != -1) ans = max(ans, block_max[block] + q);
		}

		for (; l <= r; l++) {
			int q = get(l + 1, r + 1, w[l]);
			if (q != -1) ans = max(ans, w[l] + q);
		}

		if (ans <= k) {
			cout << 1 << '\n';
		}
		else {
			cout << 0 << '\n';
		}
	}
	return 0;
}

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