oj.uz

Submission #883863

# Submission time Handle Problem Language Result Execution time Memory
883863 2023-12-06T08:23:22 Z serifefedartar Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 250908 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 +  100;

vector<int> w, mst[4*MAXN];
int ans[4*MAXN];
void merge(int k, int a, int b) {
	vector<int> A = mst[2*k];
	vector<int> B = mst[2*k+1];
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());

	int mx_B = -2e9;
	while (A.size() || B.size()) {
		int valA = (A.size() ? A.back() : 2e9);
		int valB = (B.size() ? B.back() : 2e9);
		if (valA <= valB) {
			mst[k].push_back(valA);
			ans[k] = max(ans[k], valA + mx_B);
			A.pop_back();
		} else {
			mst[k].push_back(valB);
			mx_B = max(mx_B, valB);
			B.pop_back();
		}
	}
}

void init(int k, int a, int b) {
	if (a == b) {
		ans[k] = 0;
		mst[k].push_back(w[a]);
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	merge(k, a, b);
}

pair<int,int> query(int k, int a, int b, int q_l, int q_r, int mx) {
	if (b < q_l || a > q_r)
		return {-2e9, -2e9};
	if (q_l <= a && b <= q_r) {
		auto lb = lower_bound(mst[k].begin(), mst[k].end(), mx);
		if (lb == mst[k].begin() || mst[k].size() == 0)
			return {mst[k].back(), ans[k]};
		return {mst[k].back(), max(ans[k], mx + *prev(lb))};
	}
	pair<int,int> Q1 = query(2*k, a, (a+b)/2, q_l, q_r, mx);
	pair<int,int> Q2 = query(2*k+1, (a+b)/2+1, b, q_l, q_r, max(mx, Q1.f));
	pair<int,int> new_p = {max(Q1.f, Q2.f), max(Q1.s, Q2.s)};
	return new_p;
}

int main() {
	fast
	int N, M;
	cin >> N >> M;

	w = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> w[i];
	init(1, 1, N);

	for (int i = 0; i < M; i++) {
		int l, r, k;
		cin >> l >> r >> k;

		int Q = query(1, 1, N, l, r, -2e9).s;
		if (Q > k)
			cout << "0\n";
		else
			cout << "1\n";
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 95308 KB Output is correct
2 Correct 21 ms 95320 KB Output is correct
3 Incorrect 21 ms 95324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 95308 KB Output is correct
2 Correct 21 ms 95320 KB Output is correct
3 Incorrect 21 ms 95324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 250908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 95308 KB Output is correct
2 Correct 21 ms 95320 KB Output is correct
3 Incorrect 21 ms 95324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 95308 KB Output is correct
2 Correct 21 ms 95320 KB Output is correct
3 Incorrect 21 ms 95324 KB Output isn't correct
4 Halted 0 ms 0 KB -