| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 488645 | grt | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <wall.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int INF = 1e9;
int n, k;
struct Node {
int h, H;
bool which;
};
Node T[(1 << 21)];
void prop(int x) {
if(T[x].h != 0 || T[x].H != INF) {
T[2*x].which = T[x].which;
T[2*x+1].which = T[x].which;
}
T[2*x].h = max(T[2*x].h, T[x].h);
T[2*x].H = min(T[2*x].H, T[x].H);
T[2*x+1].h = max(T[2*x+1].h, T[x].h);
T[2*x+1].H = min(T[2*x+1].H, T[x].H);
T[x].h = 0; T[x].H = INF;
}
void init(int l, int r, int v) {
T[v].h = 0; T[v].H = INF;
if(l == r) return;
int mid = (l + r)/2;
init(l,mid,v*2);
init(mid+1,r,v*2+1);
}
void upd(int a, int b, int l, int r, int v, int x, bool t) {
if(a <= l && r <= b) {
if(!t) {
T[v].h = max(T[v].h, x);
} else {
T[v].H = min(T[v].H, x);
}
T[v].which = t;
return;
}
prop(v);
int mid = (l + r) / 2;
if(a <= mid) upd(a,b,l,mid,v*2,x,t);
if(mid < b) upd(a,b,mid+1,r,v*2+1,x,t);
}
void rec(int l, int r, int v, vi &ans) {
if(l == r) {
if(T[v].h < T[v].H) ans[l] = T[v].h;
else if(!T[v].which) ans[l] = T[v].h;
else ans[l] = T[v].H;
return;
}
prop(v);
int mid = (l+r)/2;
rec(l,mid,v*2,ans);
rec(mid+1,r,v*2+1,ans);
}
void buildWall(int _n, int _k, vi op, vi l, vi r, vi hei, vi &ans) {
n = _n; k = _k;
init(0, n-1, 1);
for(int i = 0; i < k; ++i) {
upd(l[i], r[i], 0, n-1, 1, hei[i], op[i] - 1);
}
rec(0,n-1,1,ans);
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int _n, _k;
//cin >> _n >> _k;
//vi op(_k),
//for(int
//}