oj.uz

Submission #990520

# Submission time Handle Problem Language Result Execution time Memory
990520 2024-05-30T15:22:49 Z ToniB Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1340 ms 210628 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 2 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 2 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 2 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 2 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -