oj.uz

Submission #796116

# Submission time Handle Problem Language Result Execution time Memory
796116 2023-07-28T06:37:01 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 179028 KB 
#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.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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