| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301392 | tamir1 | 장애물 (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
static int N, M;
static vector<int> Tval, Hval;
static vector<int> c;
static vector<int> b;
// Segment trees
static vector<int> seg_min, seg_max;
// Build segment trees
void build_seg_min(int node, int l, int r) {
if (l == r) {
seg_min[node] = Hval[l];
return;
}
int mid = (l + r) / 2;
build_seg_min(2*node, l, mid);
build_seg_min(2*node+1, mid+1, r);
seg_min[node] = min(seg_min[2*node], seg_min[2*node+1]);
}
void build_seg_max(int node, int l, int r) {
if (l == r) {
seg_max[node] = Hval[l];
return;
}
int mid = (l + r) / 2;
build_seg_max(2*node, l, mid);
build_seg_max(2*node+1, mid+1, r);
seg_max[node] = max(seg_max[2*node], seg_max[2*node+1]);
}
// Query min in range [ql, qr]
int query_min(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INT_MAX;
if (ql <= l && r <= qr) return seg_min[node];
int mid = (l + r) / 2;
return min(query_min(2*node, l, mid, ql, qr),
query_min(2*node+1, mid+1, r, ql, qr));
}
// Query max in range [ql, qr]
int query_max(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INT_MIN;
if (ql <= l && r <= qr) return seg_max[node];
int mid = (l + r) / 2;
return max(query_max(2*node, l, mid, ql, qr),
query_max(2*node+1, mid+1, r, ql, qr));
}
// Wrappers to match your style
int call_min(int l, int r) {
return query_min(1, 0, M-1, l, r);
}
int call_max(int l, int r) {
return query_max(1, 0, M-1, l, r);
}
void initialize(vector<int> T, vector<int> H) {
Tval = T; Hval = H;
N = Tval.size(); M = Hval.size();
int d = Tval[0];
c.assign(M, 0);
b.assign(M, -1);
for(int i = 0; i < M; i++) {
if(Hval[i] >= d) c[i] = 1;
else c[i] = 0;
}
vector<int> sum(M, 0);
sum[0] = c[0];
for(int i = 1; i < M; i++) sum[i] = sum[i-1] + c[i];
vector<int> right(M), left(M);
int last = M;
for(int i = M-1; i >= 0; i--) {
if(c[i] == 1) last = i;
right[i] = last-1;
}
last = -1;
for(int i = 0; i < M; i++) {
if(c[i] == 1) last = i;
left[i] = last+1;
}
// Initialize segment trees
seg_min.assign(4*M, INT_MAX);
seg_max.assign(4*M, INT_MIN);
build_seg_min(1, 0, M-1);
build_seg_max(1, 0, M-1);
}
bool can_reach(int L, int R, int S, int D) {
bool st=false, en=false;
if(S > D) swap(S,D);
if(call_max(S,D)>=3) return false;
int sad = left[S];
int happy = right[S];
if(call_min(sad, happy) == 0) st = true;
sad = left[D];
happy = right[D];
if(call_min(sad, happy) == 0) en = true;
if(st && en) return true;
if(sum[D]-sum[S-1]==0) return true;
return false;
}