| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 374864 | Alex_tz307 | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
struct Segtree {
int Size;
vector<pair<int,int>> tree;
vector<pair<bool,int>> lazy_min, lazy_max;
void init(int N) {
Size = 1;
while(Size < N)
Size <<= 1;
tree.assign((Size << 1) + 1, make_pair(INT_MAX, 0));
lazy_min.assign((Size << 1) + 1, make_pair(false, INT_MAX));
lazy_max.assign((Size << 1) + 1, make_pair(false, 0));
}
void propagate(int x, int lx, int rx) {
if(lx == rx)
return;
if(lazy_min[x].first) {
tree[x << 1].first = min(tree[x << 1].first, lazy_min[x].second);
tree[(x << 1) | 1].first = min(tree[(x << 1) | 1].first, lazy_min[x].second);
tree[x << 1].second = min(tree[x << 1].first, tree[x << 1].second);
tree[(x << 1) | 1].second = min(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
lazy_min[x << 1].first = lazy_min[(x << 1) | 1].first = true;
lazy_min[x << 1].second = min(lazy_min[x << 1].second, lazy_min[x].second);
lazy_min[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_min[x].second);
if(lazy_max[x << 1].first)
lazy_max[x << 1].second = min(lazy_min[x << 1].second, lazy_max[x << 1].second);
if(lazy_max[(x << 1) | 1].first)
lazy_max[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
lazy_min[x] = make_pair(false, INT_MAX);
}
if(lazy_max[x].first) {
tree[x << 1].second = max(tree[x << 1].second, lazy_max[x].second);
tree[(x << 1) | 1].second = max(tree[(x << 1) | 1].second, lazy_max[x].second);
tree[x << 1].first = max(tree[x << 1].first, tree[x << 1].second);
tree[(x << 1) | 1].first = max(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
lazy_max[x << 1].first = lazy_max[(x << 1) | 1].first = true;
lazy_max[x << 1].second = max(lazy_max[x << 1].second, lazy_max[x].second);
lazy_max[(x << 1) | 1].second = max(lazy_max[(x << 1) | 1].second, lazy_max[x].second);
if(lazy_min[x << 1].first)
lazy_min[x << 1].second = max(lazy_min[x << 1].second, lazy_max[x << 1].second);
if(lazy_min[(x << 1) | 1].first)
lazy_min[(x << 1) | 1].second = max(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
lazy_max[x] = make_pair(false, 0);
}
}
void maximize(int x, int lx, int rx, int st, int dr, int h) {
propagate(x, lx, rx);
if(st <= lx && rx <= dr) {
tree[x].second = max(tree[x].second, h);
tree[x].first = max(tree[x].first, tree[x].second);
lazy_max[x].first = true;
lazy_max[x].second = max(lazy_max[x].second, h);
return;
}
int mid = (lx + rx) >> 1;
if(st <= mid)
maximize(x << 1, lx, mid, st, dr, h);
if(mid < dr)
maximize((x << 1) | 1, mid + 1, rx, st, dr, h);
}
void minimize(int x, int lx, int rx, int st, int dr, int h) {
propagate(x, lx, rx);
if(st <= lx && rx <= dr) {
tree[x].first = min(tree[x].first, h);
tree[x].second = min(tree[x].second, tree[x].first);
lazy_min[x].first = true;
lazy_min[x].second = min(lazy_min[x].second, h);
return;
}
int mid = (lx + rx) >> 1;
if(st <= mid)
minimize(x << 1, lx, mid, st, dr, h);
if(mid < dr)
minimize((x << 1) | 1, mid + 1, rx, st, dr, h);
}
int query(int x, int lx, int rx, int poz) {
propagate(x, lx, rx);
if(lx == rx)
return tree[x].second;
int mid = (lx + rx) >> 1;
if(poz <= mid)
return query(x << 1, lx, mid, poz);
else
return query((x << 1) | 1, mid + 1, rx, poz);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segtree tree;
tree.init(N);
for(int i = 0; i < k; ++i)
if(op[i] == 1)
tree.maximize(1, 1, N, left[i] + 1, right[i] + 1, height[i]);
else
tree.minimize(1, 1, N, left[i] + 1, right[i] + 1, height[i]);
for(int i = 0; i < N; ++i)
finalHeight[i] = tree.query(1, 1, N, i + 1)
}