제출 #1251707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251707		Zicrus	장애물 (IOI25_obstacles)	C++20	0 / 100	62 ms	38704 KiB

obstacles

#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;

struct segment_tree {
	struct node {
		pll mn, mx;
	};
	ll nt, n;
	vector<node> tree;

	segment_tree() { }
	segment_tree(ll n, vector<int> a) : n(n) {
		nt = 1;
		while (nt < n) nt *= 2;
		tree = vector<node>(2*nt, {{inf, 0}, {-inf, 0}});
		for (ll i = 0; i < a.size(); i++) {
			tree[nt+i] = {{a[i], i}, {a[i], i}};
		}
		for (ll i = nt-1; i > 0; i--) {
			tree[i].mn = min(tree[2*i].mn, tree[2*i+1].mn);
			tree[i].mx = max(tree[2*i].mx, tree[2*i+1].mx);
		}
	}

	pll range_min(ll k, ll tl, ll tr, ll l, ll r) {
		if (r < tl || l > tr) return {inf, -1};
		if (l <= tl && r >= tr) return tree[k].mn;
		ll mid = tl + (tr - tl) / 2;
		return min(range_min(2*k, tl, mid, l, r), range_min(2*k+1, mid+1, tr, l, r));
	}
	pll range_min(ll l, ll r) { return range_min(1, 0, nt-1, l, r); }

	pll range_max(ll k, ll tl, ll tr, ll l, ll r) {
		if (r < tl || l > tr) return {-inf, 0};
		if (l <= tl && r >= tr) return tree[k].mx;
		ll mid = tl + (tr - tl) / 2;
		return max(range_max(2*k, tl, mid, l, r), range_max(2*k+1, mid+1, tr, l, r));
	}
	pll range_max(ll l, ll r) { return range_max(1, 0, nt-1, l, r); }

	ll first_ge(ll k, ll tl, ll tr, ll l, ll v) {
		if (l > tr || tree[k].mx.first < v) return n;
		ll mid = tl + (tr - tl) / 2;
		ll res = first_ge(2*k, tl, mid, l, v);
		if (res < n) return res;
		return first_ge(2*k+1, mid+1, tr, l, v);
	}
	ll first_ge(ll l, ll v) { return first_ge(1, 0, nt-1, l, v); }

	ll first_le(ll k, ll tl, ll tr, ll l, ll v) {
		if (l > tr || tree[k].mn.first > v) return n;
		ll mid = tl + (tr - tl) / 2;
		ll res = first_le(2*k, tl, mid, l, v);
		if (res < n) return res;
		return first_le(2*k+1, mid+1, tr, l, v);
	}
	ll first_le(ll l, ll v) { return first_le(1, 0, nt-1, l, v); }

	ll last_ge(ll k, ll tl, ll tr, ll r, ll v) {
		if (tl > r || tree[k].mx.first < v) return -1;
		ll mid = tl + (tr - tl) / 2;
		ll res = last_ge(2*k+1, mid+1, tr, r, v);
		if (res >= 0) return res;
		return last_ge(2*k, tl, mid, r, v);
	}
	ll last_ge(ll r, ll v) { return last_ge(1, 0, nt-1, r, v); }

	ll last_le(ll k, ll tl, ll tr, ll r, ll v) {
		if (tl > r || tree[k].mn.first > v) return -1;
		ll mid = tl + (tr - tl) / 2;
		ll res = last_le(2*k+1, mid+1, tr, r, v);
		if (res >= 0) return res;
		return last_le(2*k, tl, mid, r, v);
	}
	ll last_le(ll r, ll v) { return last_le(1, 0, nt-1, r, v); }
};

vector<int> T, H;
segment_tree tree_T, tree_H;

void initialize(vector<int> _T, vector<int> _H) {
	T = _T; H = _H;
	ll n = T.size(), m = H.size();
	tree_T = segment_tree(n, T);
	tree_H = segment_tree(m, H);
}

pll find_best(ll s) {
	ll n = T.size(), m = H.size();
	auto safe = [&](ll i, ll j) -> bool {
		return T[i] > H[j];
	};
	ll i = 0, j = s;
	auto improve_i = [&]() -> bool {
		// maximize T
		ll mn_i = tree_T.last_le(i, H[j]) + 1;
		ll mx_i = tree_T.first_le(i, H[j]) - 1;
		auto [val, pos] = tree_T.range_max(mn_i, mx_i);
		if (val <= T[i]) return false;
		i = pos;
		return true;
	};
	auto improve_j = [&]() -> bool {
		// minimize H
		ll mn_j = tree_H.last_ge(i, T[i]) + 1;
		ll mx_j = tree_H.first_ge(i, T[i]) - 1;
		auto [val, pos] = tree_H.range_min(mn_j, mx_j);
		if (val >= H[j]) return false;
		j = pos;
		return true;
	};
	while (true) {
		bool improved = false;
		improved |= improve_i();
		improved |= improve_j();
		return {0, 0};
		if (!improved) break;
	}
	// make unique
	for (ll k = i-1; k >= 0; k--) {
		//assert(T[k] <= T[i]);
		if (T[k] >= T[i]) i = k;
	}
	for (ll k = j-1; k >= 0; k--) {
		//assert(H[k] >= H[j]);
		if (H[k] <= H[j]) j = k;
	}
	return {i, j};
}

bool can_reach(int L, int R, int S, int D) {
	pll s = find_best(S);
	pll d = find_best(D);
	return s == d;
}

#ifdef TEST
#include "grader.cpp"
#endif

• 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