Submission #883853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883853	2023-12-06T08:07:44 Z	serifefedartar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3000 ms	262144 KB

sortbooks

#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())
			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, 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, 0).s;
		if (Q > k)
			cout << "0\n";
		else
			cout << "1\n";
	}
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	95320 KB	Output is correct
2	Correct	22 ms	95576 KB	Output is correct
3	Incorrect	20 ms	95320 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	95320 KB	Output is correct
2	Correct	22 ms	95576 KB	Output is correct
3	Incorrect	20 ms	95320 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2854 ms	248696 KB	Output is correct
2	Correct	2814 ms	247424 KB	Output is correct
3	Correct	2930 ms	262144 KB	Output is correct
4	Execution timed out	3097 ms	262144 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-