Submission #1297832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297832		SabaKharebava	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	2095 ms	30180 KiB

obstacles

#include<bits/stdc++.h>

using namespace std;

const int mxN = 200000;
int seg_tree[4*mxN+1], n, color[mxN];
vector<pair<int, int>> empt[mxN];

void stree(int u, int l, int r, vector<int> &T) {
	if (l >= n || r < 0 || l > r)
		return;
	if (l == r) {
		seg_tree[u] = T[l];
		return;
	}

	int mid = (l+r)/2;
	stree(2*u, l, mid, T);
	stree(2*u + 1, mid+1, r, T);

	seg_tree[u] = min(seg_tree[2*u], seg_tree[2*u + 1]);
}

vector<pair<int, int>> normalized(vector<pair<int, int>> a) {
	if (a.empty())
		return {};
	vector<pair<int, int>> ans;
	ans.push_back(a[0]);
	pair<int, int> p;
	for (int i = 1; i < a.size(); i++)
		if (ans[ans.size()-1].second == a[i].first-1) {
			p.first = ans.back().first;
			p.second = a[i].second;
			ans.pop_back();
			ans.push_back(p);
		} else
			ans.push_back(a[i]);
	return ans;
}

vector<pair<int, int>> query(int u, int l, int r, int val) {
	//cout<< '\n' << "QUERY. " << u << ' ' << l << ' ' << r << ' ' << val << ' ' << seg_tree[u] << '\n';
	if (l >= n || r < 0 || l > r)
		return {};
	if (seg_tree[u] > val) {
		//cout<< "returned\n";
		return {make_pair(l, r)};
	}
	if (l == r)
		return {};
	int mid = (l+r)/2;
	vector<pair<int, int>> a = query(2*u, l, mid, val);
	vector<pair<int, int>> b = query(2*u + 1, mid+1, r, val);

	a.insert(a.end(), b.begin(), b.end());
	return a;
}

vector<pair<int, int>> transfer(vector<pair<int, int>> a, vector<pair<int, int>> b) {
	vector<pair<int, int>> ans;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	// a -> b

	while (!a.empty() && !b.empty()) {
		pair<int, int> A = a.back();
		pair<int, int> B = b.back();

		if (A.first > B.second)
			b.pop_back();
		else if (B.first > A.second)
			a.pop_back();
		else {
			ans.push_back(B);
			b.pop_back();
		}
	}
	
	return ans;
}

void initialize(vector<int> T, vector<int> H){
	n = T.size();
	memset(seg_tree, INT_MAX, sizeof seg_tree);
	memset(color, -1, sizeof color);
	stree(1, 0, n-1, T);

	for (int i = 0; i < H.size(); i++) {
		//cout<< i << " :\n";
		//empt[i] = normalized(query(1, 0, n-1, H[i]));
		empt[i] = query(1, 0, n-1, H[i]);
		//cout<< "\nempt\n";
		//for (auto &[a, b] : empt[i]) {
		//	cout<< "\t(" << a << "; " << b << ")\n";
		//}
	}

	map<int, int> to;
	for (int i = 0; i < H.size(); i++)
		to[i] = -1;
	for (int i = 0; i < H.size(); i++) {
		if (T[0] <= H[i])
			continue;

		if (color[i] == -1) {
			color[i] = i;
			vector<pair<int, int>> opn = empt[i];
			for (int j = i+1; j < H.size(); j++) {
				opn = transfer(opn, empt[j]);
				if (opn.empty())
					break;
				if (opn[0].first == 0) {
					if (color[j] != -1) {
						to[i] = color[j];
						break;
					}	
					color[j] = i;
				}
			}
		}
	}
	for (int i = 0; i < H.size(); i++)
		if (color[i] != -1)
			color[i] = max(color[i], to[color[i]]);

	vector<int> bt(H.size(), 0);

	/*
	cout<< "COLOR :\n";
	for (int i = 0; i < H.size(); i++)
		cout<< color[i] << ' ';
	cout<< '\n';
	*/
}

bool can_reach(int L, int R, int S, int D){
	return (color[S] == color[D]);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17