Submission #990520

#	Time	Username	Problem	Language	Result	Execution time	Memory
990520		ToniB	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1340 ms	210628 KiB

sortbooks

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

const int N = 1e6 + 2;
const int LOG = 20;
const int OFF = 1 << (LOG + 1);

int n, q, w[N], tour[OFF], L[N], R[N];
int cnt[N][LOG], bl[N][LOG];

int mrg(int i, int j) {
	if (i == -1) return j;
	if (j == -1) return i;
	if (w[i] > w[j]) return i;
	return j;
}

void con(int x, int l, int r) {
	if (l == r) {
		tour[x] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	con(x * 2 + 1, l, mid);
	con(x * 2 + 2, mid + 1, r);
	tour[x] = mrg(tour[x * 2 + 1], tour[x * 2 + 2]);
}
int f(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return tour[x];
	if (ql > r || l > qr) return -1;
	int mid = (l + r) >> 1;
	return mrg(f(x * 2 + 1, l, mid, ql, qr), f(x * 2 + 2, mid + 1, r, ql, qr));
}

void rek(int l, int r, int mx) {
	if (l < mx) {
		L[mx] = f(0, 0, n - 1, l, mx - 1);
		rek(l, mx - 1, L[mx]);
	}
	if (mx < r) {
		R[mx] = f(0, 0, n - 1, mx + 1, r);
		rek(mx + 1, r, R[mx]);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> q;
	for (int i = 0; i <= n; ++i) {
		L[i] = R[i] = n;
	}
	for (int i = 0; i < n; ++i) cin >> w[i];
	con(0, 0, n - 1);
	rek(0, n - 1, tour[0]);
	
	for (int i = 0; i <= n; ++i) {
		bl[i][0] = L[i];
		cnt[i][0] = R[i] != n;
	}
	
	for (int j = 1; j < LOG; ++j) {
		for (int i = 0; i <= n; ++i) {
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
			cnt[i][j] = cnt[i][j - 1] + cnt[bl[i][j - 1]][j - 1];
		}
	}
	
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k, --l, --r;
		int idx = f(0, 0, n - 1, l, r), ans = 0;
		if (idx < r) {
			int nxt = f(0, 0, n - 1, idx + 1, r);
			ans = max(ans, w[idx] + w[nxt]);
		}
		idx = L[idx];
		for (int i = LOG - 1; i >= 0; --i) {
			if (!cnt[idx][i]) idx = bl[idx][i];
		}
		if (R[idx] != n && idx >= l) {
			ans = max(ans, w[idx] + w[R[idx]]);
		}
		cout << (ans <= k) << "\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