oj.uz

Submission #990523

# Submission time Handle Problem Language Result Execution time Memory
990523 2024-05-30T15:24:00 Z ToniB Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1161 ms 22156 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], tour[OFF], L[N], R[N];

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]);

	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];
		while (R[idx] == n && idx >= l && idx != n) {
			idx = L[idx];
		}
		if (idx != n && idx >= l) {
			ans = max(ans, w[idx] + w[R[idx]]);
		}
		cout << (ans <= k) << "\n";
	}
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 1161 ms 22156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 12940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -