Submission #1299508

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

obstacles

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

class seg_tree {
private:
	int n;
	int tree[800000];

	void build(int u, int l, int r, vector<int> &v) {
		if (l > r || r < 0 || l >= n)
			return;
		if (l == r) {
			tree[u] = v[l];
			return;
		}

		int mid = (l+r)/2;
		build(2*u, l, mid, v);
		build(2*u + 1, mid+1, r, v);

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

	int query(int u, int l, int r, int ql, int qr) {
		if (l > r || r < 0 || l >= n)
			return INT_MAX;
		if (ql <= l && qr >= r)
			return tree[u];
		if (l == r || r < ql || l > ql)
			return INT_MAX;

		int mid = (l+r)/2;
		return min(query(2*u, l, mid, ql, qr), query(2*u + 1, mid+1, r, ql, qr));
	}

public:
	void build(vector<int> &v) {
		n = v.size();
		build(1, 0, n-1, v);
	}

	int query(int l, int r) {
		return query(1, 0, n-1, l, r);
	}
};

pair<int, int> reach[200000];
int lvl[200000];
vector<int> inc = {0}, mx, t;
seg_tree tree;

void initialize(vector<int> T, vector<int> H) {
	t = T;
	tree.build(H);
	mx.pb(T[0]);
	for (int i = 1; i < T.size(); i++) {
		if (T[inc.back()] < T[i])
			inc.pb(i);
		mx.pb(min(mx.back(), T[i]));
	}
	
	for (int i = 0; i < H.size(); i++) {
		if (H[i] >= T[0]) {
			reach[i].first = -1;
			reach[i].second = -1;
			continue;
		}
		
		int j = i;
		while (j+1 < H.size() && H[j+1] < T[0])
			j++;

		int seg_l = i, seg_r = j;
		int l = 0, r = inc.size(), mid, mn = tree.query(seg_l, seg_r);
		int lv;
		while (l < r) {
			mid = (l+r)/2;
			if (mx[inc[mid]] <= mn)
				r = mid;
			else {
				lv = mid;
				l = mid+1;
			}
		}

		while (seg_l-1 >= 0 && T[inc[lv]] > H[seg_l-1])
			seg_l--;
		while (seg_r+1 < H.size() && T[inc[lv]] > H[seg_r+1])
			seg_r++;

		for (int ind = i; ind <= j; ind++) {
			lvl[ind] = inc[lv];
			reach[ind].first = seg_l;
			reach[ind].second = seg_r;
		}
		i = j;
	}
	/*
	cout<< "REACH :\n";
	for (int i = 0; i < H.size(); i++)
		cout<< i << " -> (" << reach[i].first << "; " << reach[i].second << ")\n";
	*/
}

bool can_reach(int L, int R, int S, int D) {
	if (S == D || reach[S].first == reach[D].first && reach[S].second == reach[D].second)
		return true;

	int lv = max(lvl[S], lvl[D]);
	int l = max(reach[S].first, reach[D].first);
	int r = min(reach[S].second, reach[D].second);

	if (l > r)
		return false;
	int mn = tree.query(l, r);
	return (mn < mx[lv]);
}

• 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