| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1039844 | Thunnus | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
struct SegTree{
struct node{
int min = 0, max = LLONG_MAX;
};
vector<node> st;
SegTree(int n) : st(4 * n) {}
inline combine(const node &a, const node &b){
node c;
c.min = max(a.min, b.min);
c.max = min(a.max, b.max);
return c;
}
inline void apply(int p, int v){
st[v].min = max(st[p].min, st[v].min);
st[v].min = min(st[p].max, st[v].min);
st[v].max = min(st[p].max, st[v].max);
st[v].max = max(st[p].min, st[v].max);
}
inline void propagate(int v){
apply(v, 2 * v);
apply(v, 2 * v + 1);
}
void update(int l, int r, int val, int type, int v, int tl, int tr){
if(l > tr || r < tl) return;
if(tl >= l && tr <= r){
if(type == 1)
st[v].min = max(st[v].min, val);
else
st[v].max = min(st[v].max, val);
return;
}
int mid = (tl + tr) / 2;
propagate(v);
update(l, r, val, type, 2 * v, tl, mid);
update(l, r, val, type, 2 * v + 1, mid + 1, tr);
st[v] = combine(st[2 * v], st[2 * v + 1]);
}
void query(int a[], int v, int tl, int tr){
if(tl == tr){
a[tl - 1] = st[v].min;
return;
}
int mid = (tl + tr) / 2;
propagate(v);
query(a, 2 * v, tl, mid);
query(a, 2 * v + 1, mid + 1, tr);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree st(n);
for(int i = 0; i < k; i++){
st.update(left[i], right[i], height[i], op[i], 1, 1, n);
}
st.query(finalHeight, 1, 1, n);
return finalHeight;
}