| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 683501 | speedyArda | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e6 + 5;
const int inf = 1e9 + 7;
struct Node {
int mx = inf;
int mn = 0;
}
seg[MAXN * 4];
void push(int v)
{
seg[2 * v].mn = min(seg[v].mx, max(seg[v * 2].mn, seg[v].mn));
seg[2 * v].mx = max(seg[v].mn, min(seg[2 * v].mx, seg[v].mx));
seg[2 * v + 1].mn = min(seg[v].mx, max(seg[v * 2 + 1].mn, seg[v].mn));
seg[2 * v + 1].mx = max(seg[v].mn, min(seg[2 * v + 1].mx, seg[v].mx));
seg[v].mn = 0;
seg[v].mx = inf;
}
void update(int v, int tl, int tr, int l, int r, int val, int type)
{
if(l > r)
return;
if(l <= tl && r >= tr)
{
if(type == 1)
{
seg[v].mx = max(seg[v].mx, val);
seg[v].mn = max(seg[v].mn, val);
} else
{
seg[v].mx = min(seg[v].mx, val);
seg[v].mn = min(seg[v].mn, val);
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(tm, r), val, type);
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val, type);
}
int get(int v, int tl, int tr, int pos)
{
if(tl == tr)
return seg[v].mn;
push(v);
int tm = (tl + tr) / 2;
if(tm >= pos)
return get(2 * v, tl, tm, pos);
else
return get(2 * v + 1, tm + 1, tr, pos);
}
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < k; i++) {
update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = get(1, 0, n - 1, i);
}
}