Submission #1260254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260254		software1146	Obstacles for a Llama (IOI25_obstacles)	C++17	100 / 100	1471 ms	620920 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
struct Mnt {
	vector<vector<int>> table;
	void init (int n, vector<int> v) {
		table.clear();
		table.resize(32-__builtin_clz(n));
		table[0] = v;
		for (size_t i = 1; i < table.size(); i++) for (int j = 0; j <= n-(1<<i); j++)
			table[i].push_back(min(table[i-1][j], table[i-1][j+(1<<i-1)]));
	}
	int query (int l, int r) {
		int x = 31-__builtin_clz(r-l);
		return min(table[x][l], table[x][r-(1<<x)]);
	}
};
struct Mxt {
	vector<vector<int>> table;
	void init (int n, vector<int> v) {
		table.clear();
		table.resize(32-__builtin_clz(n));
		table[0] = v;
		for (size_t i = 1; i < table.size(); i++) for (int j = 0; j <= n-(1<<i); j++)
			table[i].push_back(max(table[i-1][j], table[i-1][j+(1<<i-1)]));
	}
	int query (int l, int r) {
		int x = 31-__builtin_clz(r-l);
		return max(table[x][l], table[x][r-(1<<x)]);
	}
};
vector<Mnt> bl;
vector<Mxt> br;
int n, m;
vector<int> t, h;
Mxt mxt;
Mnt mnt;
void initialize (vector<int> T, vector<int> H) {
	t = T;
	h = H;
	n = t.size();
	m = h.size();
	mxt.init(m, h);
	mnt.init(n, t);
	vector<vector<pair<int, int>>> blift;
	blift.resize(20, vector<pair<int, int>>(m));
	bl.resize(20);
	br.resize(20);
	Mxt bruh;
	bruh.init(n, t);
	for (int i = 0; i < m; i++) {
		int down = 0;
		for (int j = 20; j--;) if (down+(1<<j) <= n && mnt.query(0, down+(1<<j)) > h[i])
			down += 1<<j;
		blift[0][i] = {i, i+1};
		if (down) {
			for (int j = 20; j--;) {
				if (blift[0][i].f-(1<<j) >= 0 && mxt.query(blift[0][i].f-(1<<j), i) < bruh.query(0, down))
					blift[0][i].f -= 1<<j;
				if (blift[0][i].s+(1<<j) <= m && mxt.query(i, blift[0][i].s+(1<<j)) < bruh.query(0, down))
					blift[0][i].s += 1<<j;
			}
		}
	}
	for (int i = 1; i < 20; i++) {
		vector<int> a, b;
		for (auto j: blift[i-1]) {
			a.push_back(j.f);
			b.push_back(j.s);
		}
		bl[i-1].init(m, a);
		br[i-1].init(m, b);
		for (int j = 0; j < m; j++) {
			blift[i][j].f = bl[i-1].query(blift[i-1][j].f, blift[i-1][j].s);
			blift[i][j].s = br[i-1].query(blift[i-1][j].f, blift[i-1][j].s);
		}
	}
	vector<int> a, b;
	for (auto j: blift.back()) {
		a.push_back(j.f);
		b.push_back(j.s);
	}
	bl.back().init(m, a);
	br.back().init(m, b);
}
bool can_reach (int l, int r, int a, int b) {
	if (h[a] >= t[0] || h[b] >= t[0]) return 0;
	r++;
	int la, ra, lb, rb;
	{
		int x = a, y = a+1;
		for (int i = 20; i--;) {
			if (bl[i].query(x, y) >= l && br[i].query(x, y) <= r) {
				int c = bl[i].query(x, y);
				y = br[i].query(x, y);
				x = c;
			}
		}
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		la = x;
		ra = y;
	}
	{
		int x = b, y = b+1;
		for (int i = 20; i--;) {
			if (bl[i].query(x, y) >= l && br[i].query(x, y) <= r) {
				int c = bl[i].query(x, y);
				y = br[i].query(x, y);
				x = c;
			}
		}
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		y = min(r, br[0].query(x, y));
		x = max(l, bl[0].query(x, y));
		lb = x;
		rb = y;
	}
	return la == lb && ra == rb;
}

• 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: 17 / 17