Submission #1297243

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

obstacles

/*
	to future me:
	I have no fucking idea what the fuck is going on, I have no idea if the code should work, good luck in debugging it lmfao.

	update:
	there are no longer any errors, the dfs function is fucked as it goes on in an infinite loop so fix that.
*/

#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]));
		//cout<< "\nempt\n";
		//for (auto &[a, b] : empt[i]) {
		//	cout<< "\t(" << a << "; " << b << ")\n";
		//}
	}
	
	vector<int> bt(H.size(), 0);
	auto dfs = [&](auto &dfs, int i, int val, vector<pair<int, int>> open) -> void {
		//cout<< "DFS. " << i << " -> " << val << '\n';
		//for (auto &[a, b] : open)
		//	cout<< "\t(" << a << "; " << b << ")\n";
		if (!open.empty() && open[0].first == 0) {
		//	cout<< "MARKED " << i << '\n';
			color[i] = val;
		}
		if (bt[i] > min(3, (int)empt[i].size()) || open.empty() || i < 0 || i >= H.size())
			return;
		bt[i]++;

		vector<pair<int, int>> l, r;
		if (i > 0)
			l = transfer(open, empt[i-1]);
		if (i < H.size()-1)
			r = transfer(open, empt[i+1]);
		
		dfs(dfs, i-1, val, l);
		dfs(dfs, i+1, val, r);
	};
	
	for (int i = 0; i < H.size(); i++) {
		if (T[0] > H[i] && color[i] == -1) {
			vector<pair<int, int>> opn = empt[i];
			while (opn.size() > 1)
				opn.pop_back();
			bt.resize(H.size(), 0);
			//cout<< "DFS FROM : " << i << '\n';
			dfs(dfs, i, i, opn);
			//cout<< '\n';
		}
	}
 
	//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