Submission #1298386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298386		SabaKharebava	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	2096 ms	15408 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;

	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]);
	}

	int minquery(int u, int l, int r, int il, int ir) {
		//cout<< "QUERY : " << u << ' ' << l << ' ' << r << '\n';
		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));
	}

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';
	}

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

vector<int> rg, lf;

void initialize(vector<int> T, vector<int> H){
	seg_tree hseg, tseg;
	tseg.build(T);
	hseg.build(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());
	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;
			//cout<< '\t' << l << ' ' << mid << ' ' << r << '\n';
			if (tseg.query(inc[lst], inc[mid]) <= hseg.query(seg_l, seg_r))
				r = mid;
			else {
				//cout<< "\there\n";
				lst = l;
				l = mid+1;
				r = inc.size();

				while (seg_l-1 >= 0 && H[seg_l-1] < T[inc[mid]])
					seg_l--;
				while (seg_r+1 < H.size() && H[seg_r+1] < T[inc[mid]])
					seg_r++;
			}
		}
		/*
		for (int ind = 1; ind < inc.size(); ind++) {
			if (tseg.query(inc[ind-1], inc[ind]) <= hseg.query(seg_l, seg_r))
				break;
			while (seg_l-1 >= 0 && H[seg_l-1] < T[inc[ind]])
				seg_l--;
			while (seg_r+1 < H.size() && H[seg_r+1] < T[inc[ind]])
				seg_r++;
			//cout<< '\t' << ind << " -> (" << seg_l << "; " << seg_r << ")\n";
			//cout<< "\t\t" << tseg.query(inc[ind-1], inc[ind]) << ' ' << hseg.query(seg_l, seg_r) << '\n';
		}
		*/
		for (int ind = i; ind <= j; ind++) {
			rg[ind] = seg_r;
			lf[ind] = seg_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){
	return (rg[S] == rg[D] && lf[S] == lf[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