Submission #1302735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302735		paronmanukyan	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	381 ms	141884 KiB

obstacles

//#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x)		x.begin(), x.end()
#define ll		long long
#define V		vector
#define pb		push_back
#define FASTIO		ios::sync_with_stdio(false); cin.tie(nullptr);

struct node{
	int ind, l, r, t;
};

struct edge{
	int to, lft, rgt;
};

const int N = 200000 + 5;
const int M = 16 * N;
const int LG = 19;
const int LG_C = 23;

int n, m;
V<int> t, h;

int stmn[N][LG], stmx[N][LG];
int tmn[N][LG], tmx[N][LG];
int lg2[N];

int p[M], sz_[M];
V<edge> adj[M];
int up[M][LG_C], upl[M][LG_C], upr[M][LG_C];
bool dad[M];
int dep[M];

int nd[N];
int timer = 1;
map<tuple<int,int,int>, int> mp;

void crt(int x){
	if (x >= M) assert(false);
	p[x] = x;
	sz_[x] = 1;
	dad[x] = true;
}

int find(int x){
	return p[x] == x ? x : p[x] = find(p[x]);
}

int min_rng(int l, int r){
	int j = lg2[r - l + 1];
	return min(stmn[l][j], stmn[r - (1 << j) + 1][j]);
}

int max_rng(int l, int r){
	int j = lg2[r - l + 1];
	return max(stmx[l][j], stmx[r - (1 << j) + 1][j]);
}

int mnt_rng(int l, int r){
	int j = lg2[r - l + 1];
	return min(tmn[l][j], tmn[r - (1 << j) + 1][j]);
}

int mxt_rng(int l, int r){
	int j = lg2[r - l + 1];
	return max(tmx[l][j], tmx[r - (1 << j) + 1][j]);
}

void make_edge(node x, node y){
	dad[x.ind] = false;
	int mn = mnt_rng(x.t, y.t);
	int l = x.l, r = x.r - 1, ans = x.r;
	while (l <= r) {
		int md = (l + r) >> 1;
		if (min_rng(md, x.r) < mn) ans = md, r = md - 1;
		else l = md + 1;
	}
	int nl = ans;
	l = x.l + 1; r = x.r; ans = x.l;
	while (l <= r) {
		int md = (l + r) >> 1;
		if (min_rng(md, x.r) < mn) ans = md, l = md + 1;
		else r = md - 1;
	}
	int nr = ans;
	adj[y.ind].pb({x.ind, nl, nr});
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(sz_[a] < sz_[b]) swap(a, b);
	p[b] = a;
	sz_[a] += sz_[b];
}

void expand(node x){
	if(x.l == 1 && x.r == m) return;
	if(x.t == n) return;

	int vl = min(h[x.l - 1], h[x.r + 1]);
	if(mxt_rng(x.t + 1, n) <= vl) return;

	int l = x.t + 1, r = n - 1, ans = n;
	while(l <= r){
		int md = (l + r) >> 1;
		if(mxt_rng(x.t + 1, md) <= vl) l = md + 1;
		else ans = md, r = md - 1;
	}

	if(mnt_rng(x.t + 1, ans) <= min_rng(x.l, x.r)) return;

	int nwt = ans;

	l = 1; r = x.l - 1; ans = x.l;
	while(l <= r){
		int md = (l + r) >> 1;
		if(max_rng(md, x.l) < t[nwt]) ans = md, r = md - 1;
		else l = md + 1;
	}
	int nwl = ans;

	l = x.r + 1; r = m; ans = x.r;
	while(l <= r){
		int md = (l + r) >> 1;
		if(max_rng(x.r, md) < t[nwt]) ans = md, l = md + 1;
		else r = md - 1;
	}
	int nwr = ans;

	auto key = make_tuple(nwl, nwr, nwt);
	if(mp.count(key)){
		make_edge(x, {mp[key], nwl, nwr, nwt});
	}else{
		mp[key] = timer;
		crt(timer);
		make_edge(x, {timer, nwl, nwr, nwt});
		++timer;
		expand({timer - 1, nwl, nwr, nwt});
	}
}

void dfs(int v){
	for (auto e : adj[v]) {
		int ch = e.to;
		dep[ch] = dep[v] + 1;
		up[ch][0] = v;
		upl[ch][0] = e.lft;
		upr[ch][0] = e.rgt;
		for (int i = 1; i < LG_C; ++i) {
			up[ch][i] = up[up[ch][i - 1]][i - 1];
			upl[ch][i] = max(upl[ch][i - 1], upl[up[ch][i - 1]][i - 1]);
			upr[ch][i] = min(upr[ch][i - 1], upr[up[ch][i - 1]][i - 1]);
		}
		dfs(ch);
	}
}

void tr(int root){
	for (int i = 0; i < LG_C; ++i) {
		up[root][i] = root;
		upl[root][i] = 0;
		upr[root][i] = m + 1;
	}
	dep[root] = 0;
	dfs(root);
}

bool is_s(int a, int b, int l, int r){
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b];
	for (int i = 0; i < LG_C; ++i)
		if (d & (1 << i)) {
			if (upl[a][i] > r || upr[a][i] < l) return false;
			a = up[a][i];
		}
	if (a == b) return true;
	for (int i = LG_C - 1; i >= 0; --i) {
		if (up[a][i] != up[b][i]) {
			if (upl[a][i] > r || upr[a][i] < l) return false;
			if (upl[b][i] > r || upr[b][i] < l) return false;
			a = up[a][i];
			b = up[b][i];
		}
	}
	if (upl[a][0] > r || upr[a][0] < l) return false;
	if (upl[b][0] > r || upr[b][0] < l) return false;
	return true;
}

void initialize(V<int> T, V<int> H){
	n = T.size();
	m = H.size();

	t.assign(n + 1, 0);
	h.assign(m + 2, 1e9 + 7);

	for(int i = 1; i <= n; i++) t[i] = T[i - 1];
	for(int i = 1; i <= m; i++) h[i] = H[i - 1];

	lg2[1] = 0;
	for(int i = 2; i < N; i++) lg2[i] = lg2[i >> 1] + 1;

	for(int i = 1; i <= m; i++) stmn[i][0] = stmx[i][0] = h[i];
	for(int j = 1; j < LG; j++)
		for(int i = 1; i + (1 << (j - 1)) <= m; i++){
			stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]);
			stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]);
		}

	for(int i = 1; i <= n; i++) tmn[i][0] = tmx[i][0] = t[i];
	for(int j = 1; j < LG; j++)
		for(int i = 1; i + (1 << (j - 1)) <= n; i++){
			tmn[i][j] = min(tmn[i][j - 1], tmn[i + (1 << (j - 1))][j - 1]);
			tmx[i][j] = max(tmx[i][j - 1], tmx[i + (1 << (j - 1))][j - 1]);
		}

	int ls = 1;
	bool las = false;

	for(int i = 1; i <= m + 1; i++){
		if(t[1] > h[i]){
			nd[i] = timer;
			las = true;
		}else{
			if(las){
				crt(timer);
				++timer;
				expand({timer - 1, ls, i - 1, 1});
			}
			las = false;
			ls = i + 1;
		}
	}

	for (int i = 1; i < timer; ++i) {
		for (auto e : adj[i]) {
			merge(i, e.to);
			//cout << i << " " << e.to << "\n";
		}
	}

	for(int i = 1; i < timer; i++)
		if(dad[i]) tr(i);

	//cout << nd[2] << " " << nd[6] << endl;
}

bool can_reach(int l, int r, int s, int d){
	++l; ++r; ++s; ++d;
	if (find(nd[s]) != find(nd[d])) return false;
	return is_s(nd[s], nd[d], l, r);
}

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