Submission #1299086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299086		SabaKharebava	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2096 ms	15664 KiB

obstacles

#include<bits/stdc++.h>

using namespace std;

const int mxN = 200000;

#define pb push_back

class seg_tree {
private:
	int  n;
	vector<int> tree, maxtree;

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

		int mid = (l+r)/2;
		minbuild(2*u, l, mid, V);
		minbuild(2*u + 1, mid+1, r, V);
	
		tree[u] = min(tree[2*u], tree[2*u + 1]);
	}

	void maxbuild(int u, int l, int r, vector<int> &V) {
		if (r < 0 || l >= n || l > r)
			return;
		if (l == r) {
			maxtree[u] = V[l];
			return;
		}

		int mid = (l+r)/2;
		maxbuild(2*u, l, mid, V);
		maxbuild(2*u + 1, mid+1, r, V);
	
		maxtree[u] = max(maxtree[2*u], maxtree[2*u + 1]);
	}

	int minquery(int u, int l, int r, int il, int ir) {
		if (r < 0 || l >= n || l > r)
			return INT_MAX;	
		if (il <= l && ir >= r)
			return tree[u];
		if (l == r)
			return INT_MAX;

		int mid = (l+r)/2;
		return min(minquery(2*u, l, mid, il, ir), minquery(2*u + 1, mid+1, r, il, ir));
	}

	int maxquery(int u, int l, int r, int il, int ir) {
		if (r < 0 || l >= n || l > r)
			return 0;
		if (il <= l && ir >= r)
			return maxtree[u];
		if (l == r)
			return 0;

		int mid = (l+r)/2;
		return max(maxquery(2*u, l, mid, il, ir), maxquery(2*u + 1, mid+1, r, il, ir));
	}

public:
	void build(vector<int> &T) {
		n = T.size();
		tree.resize(4*n, 1e9);
		minbuild(1, 0, n-1, T);
		//for (int i = 0; i < 4*n; i++)
		//	cout<< tree[i] << ' ';
		//cout<< '\n';
	}

	void buildmx(vector<int> &T) {
		maxtree.resize(4*n, -1);
		maxbuild(1, 0, n-1, T);
	}

	pair<int, int> open(int t, int seg_l, int seg_r) {
		int l = seg_r, r = n-1, mid;
		while (l < r) {
			mid = (l+r)/2;
			if (maxquery(1, 0, n-1, seg_r, mid) >= t)
				r = mid;
			else
				l = mid+1;
		}
		seg_r = l;

		l = 0, r = seg_l;
		while (l < r) {
			mid = (l+r)/2;
			if (maxquery(1, 0, n-1, mid, seg_l) >= t)
				l = mid+1;
			else
				r = mid;
		}
		seg_l = l;
	
		return make_pair(seg_l, seg_r);
	}

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

vector<int> rg, lf, lvl;
seg_tree hseg, tseg;

void initialize(vector<int> T, vector<int> H){
	tseg.build(T);
	hseg.build(H);
	hseg.buildmx(H);

	vector<int> inc;
	inc.pb(0);
	for (int i = 1; i < T.size(); i++)
		if (T[inc.back()] < T[i])
			inc.pb(i);

	rg.resize(H.size()); lf.resize(H.size()); lvl.resize(H.size());
	for (int i = 0; i < H.size(); i++) {
		if (T[0] <= H[i])
			continue;
		int j = i;
		while (j+1 < H.size() && T[0] > H[j+1])
			j++;

		int seg_l = i, seg_r = j;
		//cout<< i << ":\n";
		int l = 1, r = inc.size(), mid, lst = 0;
		while (l < r) {
			mid = (l+r)/2;
			if (tseg.query(inc[lst], inc[mid]) <= hseg.query(seg_l, seg_r))
				r = mid;
			else
				l = mid+1;
		}
		
		pair<int, int> opn = hseg.open(T[inc[mid]], seg_l, seg_r);
		seg_l = opn.first;
		seg_r = opn.second;
		
		for (int ind = i; ind <= j; ind++) {
			rg[ind] = seg_r;
			lf[ind] = seg_l;
			lvl[ind] = inc[l];
		}
		i = j;
	}
	
	/*
	cout<< "(LF; RG)\n";
	for (int i = 0; i < H.size(); i++)
		cout<< i << " -> (" << lf[i] << "; " << rg[i] << ")\n";
	*/
	return;
}

bool can_reach(int L, int R, int S, int D){
	if (rg[S] == rg[D] && lf[S] == lf[D])
		return true;

	int l, r, lv;
	lv = max(lvl[S], lvl[D]);
	l = max(lf[S], lf[D]);
	r = min(rg[S], rg[D]);

	if (tseg.query(0, lv) <= hseg.query(l, r))
		return false;
	return true;
}

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