Submission #796119

#	Time	Username	Problem	Language	Result	Execution time	Memory
796119		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3065 ms	147116 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+3, maxm = 1e6+3;
int n, m;
int w[maxn];
tuple<int, int, int, int> ques[maxm];
int par[maxn], sez[maxn], lb[maxn], rb[maxn];
set<int> st[maxn];
priority_queue<tuple<int, int, int>> pq;
int ans[maxn];

int find(int u) {
	if (u != par[u]) return par[u] = find(par[u]);
	return u;
} 

void unite(int u, int v) {
	u = find(u); v = find(v);
	if (sez[u] > sez[v]) swap(u, v);
	par[u] = v;
	sez[v] += sez[u];
	lb[v] = min(lb[v], lb[u]);
	rb[v] = max(rb[v], rb[u]);
	for (int x : st[u]) st[v].insert(x);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; i++) cin >> w[i];
	for (int i=0; i<m; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		ques[i] = make_tuple(k, l, r, i);
	}

	sort(ques, ques+m);
	for (int i=0; i<n; i++) {
		par[i] = lb[i] = rb[i] = i;
		sez[i] = 1;
		st[i].insert(w[i]);
		if (i > 0) pq.emplace(-(w[i-1] + w[i]), i-1, i);
	}
	for (int i=0; i<m; i++) {
		auto &[k, l, r, ai] = ques[i];
		while (!pq.empty() && -get<0>(pq.top()) <= k) {
			auto [_, ii, jj] = pq.top();
			pq.pop();
			unite(ii, jj);

			int u = find(ii);
			if (lb[u] > 0) {
				int v = find(lb[u] - 1);
				auto itv = st[v].rbegin();
				auto itu = st[u].lower_bound(*itv);
				if (itu != st[u].begin()) {
					itu--;
					pq.emplace(-(*itv + *itu), u, v);
				} else {
					pq.emplace(0, u, v);
				}
			}
			if (rb[u] + 1 < n) {
				int v = find(rb[u] + 1);
				auto itu = st[u].rbegin();
				auto itv = st[v].lower_bound(*itu);
				if (itv != st[v].begin()) {
					itv--;
					pq.emplace(-(*itv + *itu), u, v);
				} else {
					pq.emplace(0, u, v);
				}	
			}
		}

		ans[ai] = (find(l-1) == find(r-1));
	}

	for (int i=0; i<m; i++) cout << ans[i] << '\n';
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23