Submission #883863

#	Time	Username	Problem	Language	Result	Execution time	Memory
883863		serifefedartar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3062 ms	250908 KiB

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() || 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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23