| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1300746 | vache_kocharyan | 장애물 (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
const int LOG = 21;
vector<int>T, H;
int n, m;
struct sparse_table
{
vector<int>a;
int sp_mx[N][LOG];
int sp_mn[N][LOG];
int id_mn[N][LOG];
int id_mx[N][LOG];
void build_sparse(vector<int>H)
{
a = H;
for (int i = 0; i < m; i++)
{
sp_mn[i][0] = H[i];
sp_mx[i][0] = H[i];
id_mn[i][0] = i;
id_mx[i][0] = i;
}
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i + (1 << j) <= m; i++)
{
int mid = i + (1 << (j - 1));
if (sp_mx[i][j - 1] >= sp_mx[mid][j - 1]) {
sp_mx[i][j] = sp_mx[i][j - 1];
id_mx[i][j] = id_mx[i][j - 1];
}
else {
sp_mx[i][j] = sp_mx[mid][j - 1];
id_mx[i][j] = id_mx[mid][j - 1];
}
if (sp_mn[i][j - 1] <= sp_mn[mid][j - 1]) {
sp_mn[i][j] = sp_mn[i][j - 1];
id_mn[i][j] = id_mn[i][j - 1];
}
else {
sp_mn[i][j] = sp_mn[mid][j - 1];
id_mn[i][j] = id_mn[mid][j - 1];
}
}
}
}
int query_mx(int l, int r)
{
int lg = log2(r - l + 1);
return max(sp_mx[l][lg], sp_mx[r - (1 << lg) + 1][lg]);
}
int query_mn(int l, int r)
{
int lg = log2(r - l + 1);
return min(sp_mn[l][lg], sp_mn[r - (1 << lg) + 1][lg]);
}
int query_id_mx(int l, int r)
{
int lg = log2(r - l + 1);
int a = sp_mx[l][lg], b = sp_mx[r - (1 << lg) + 1][lg];
if (a >= b) return id_mx[l][lg];
return id_mx[r - (1 << lg) + 1][lg];
}
int query_id_mn(int l, int r)
{
int lg = log2(r - l + 1);
int a = sp_mn[l][lg], b = sp_mn[r - (1 << lg) + 1][lg];
if (a <= b) return id_mn[l][lg];
return id_mn[r - (1 << lg) + 1][lg];
}
}c_sp, r_sp;
bool is_free(int i, int j)
{
return T[i] > H[j];
}
int l[N], r[N], right_most_x[N], left_most_x[N], t[N], mn_ind[N];
pair<int, int>find_lr(int ind, int S)
{
int ansl, ansr;
int l = 0, r = S;
while (l <= r)
{
int mid = (l + r) / 2l;
if (r_sp.query_mx(mid, S) < T[ind])
{
ansl = mid;
l = mid - 1;
}
else
{
r = mid + 1;
}
}
l = S, r = m - 1;
while (l <= r)
{
int mid = (l + r) / 2l;
if (r_sp.query_mx(S, mid) < T[ind])
{
ansr = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return { ansl, ansr };
}
int nxt[N];
struct node
{
int ind, t;
};
map<node, int>mp;
struct dsu_
{
int p[N], sz[N];
int n;
void init(int _n)
{
n = _n;
for (int i = 1; i <= n; i++)
p[i] = i, sz[i] = 1;
}
int find(int a)
{
if (a == p[a])
return p[a];
return p[a] = find(p[p[a]]);
}
void merge(int a, int b)
{
a = find(a), b = find(b);
if (a == b)return;
if (sz[a] < sz[b])swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
bool ask(int a, int b)
{
a = find(a);
b = find(b);
if (a == b)return true;
else return false;
}
}dsu;
void initialize(std::vector<int> T, std::vector<int> H)
{
n = T.size();
m = H.size();
(::T).resize(n);
(::H).resize(m);
for (int i = 0; i < n; i++)(::T)[i] = T[i];
for (int i = 0; i < m; i++)(::H)[i] = H[i];
r_sp.build_sparse(H);
c_sp.build_sparse(T);
int cnt = 0;
queue<int>cur;
for (int i = 0; i < m;)
{
if (is_free(0, i))
{
cnt++;
cur.push(cnt);
pair<int, int>P = find_lr(0, i);
l[cnt] = P.first;
r[cnt] = P.second;
i = r[cnt] + 2;
t[cnt] = 0;
mp[{0, r_sp.query_id_mn(l[cnt], r[cnt])}] = cnt;
}
else i++;
}
while (!cur.empty()) {
int i = cur.front();
int ind = r_sp.query_id_mn(l[i], r[i]);
int x = t[i];
bool bol = true;
while (x < n)
{
if (!bol)break;
x++;
if (c_sp.query_id_mn(t[i], x) <= H[ind])
break;
pair<int, int>P;
P = find_lr(x, ind);
if (P.first <= l[i] && P.second >= r[i])
{
if (mp[{x, r_sp.query_id_mn(P.first, P.second)}]) {
break;
}
cnt++;
l[cnt] = P.first;
r[cnt] = P.second;
t[cnt] = x;
mp[{x, r_sp.query_id_mn(P.first, P.second)}] = cnt;
cur.push(cnt);
nxt[i] = cnt;
break;
}
}
}
dsu.init(cnt + 10);
for (int i = 1; i < cnt; i++)
{
if (nxt[i])
dsu.merge(i, nxt[i]);
}
}
bool can_reach(int L, int R, int S, int D)
{
if (S > D)
swap(S, D);
if (dsu.ask(S, D))return true;
else return false;
}