oj.uz

답안 #990529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990529 2024-05-30T15:35:11 Z ToniB Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1264 ms 30560 KB 
#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]]};
		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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1264 ms 30560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 13144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -