제출 #990535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990535		ToniB	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1533 ms	111088 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], L[N], R[N];

struct Node {
	int idx;
	int val;
} tour[OFF];

Node mrg(Node a, Node b) {
	Node ret = {a.idx, max(a.val, b.val)};
	if (a.idx == -1 || (b.idx != -1 && w[a.idx] <= w[b.idx])) ret.idx = b.idx;
	return ret;
}

void con(int x, int l, int r) {
	if (l == r) {
		tour[x] = {l, w[l] + w[R[l]]};
		if (R[l] == n) tour[x].val = 0;
		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]);
}
Node 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, 0};
	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).idx;
		rek(l, mx - 1, L[mx]);
	}
	if (mx < r) {
		R[mx] = f(0, 0, n - 1, mx + 1, r).idx;
		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].idx);
	con(0, 0, n - 1);

	while (q--) {
		int l, r, k;
		cin >> l >> r >> k, --l, --r;
		int idx = f(0, 0, n - 1, l, r).idx, ans = 0;
		if (idx < r) {
			int nxt = f(0, 0, n - 1, idx + 1, r).idx;
			ans = max(ans, w[idx] + w[nxt]);
		}
		if (l < idx) ans = max(ans, f(0, 0, n - 1, l, idx - 1).val);
		cout << (ans <= k) << "\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