| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302569 | paronmanukyan | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
//#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;
};
const int N = 200000 + 5;
const int LG = 19;
int n, m;
V<int> t, h;
int stmn[N][LG], stmx[N][LG]; // h
int tmn[N][LG], tmx[N][LG]; // t
int lg2[N];
int p[N * 20], sz_[N * 20];
int nd[N];
int timer = 1;
map<tuple<int,int,int>, int> mp;
void crt(int x){
p[x] = x;
sz_[x] = 1;
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
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];
}
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 up(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(nwt, nwl, nwr);
if(mp.count(key)){
merge(x.ind, mp[key]);
}else{
mp[key] = timer;
crt(timer);
merge(x.ind, timer);
up({timer, nwl, nwr, nwt});
++timer;
}
}
void initialize(const V<int>& T, const V<int>& H){
n = T.size();
m = H.size();
t.assign(n + 1, 0);
h.assign(m + 1, 0);
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;
// h sparse table
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]);
}
// t sparse table
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; i++){
if(t[1] > h[i]){
nd[i] = timer;
las = true;
}else{
if(las){
crt(timer);
up({timer, ls, i - 1, 1});
++timer;
}
las = false;
ls = i + 1;
}
}
if(las){
crt(timer);
up({timer, ls, m, 1});
++timer;
}
}