| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1111115 | TheGreatAntivirus | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include <bits/stdc++.h>
struct query
{
int mx, mn;
query()
{
mx = 0; mn = 1e9;
}
};
class segment
{
public:
void push(int v, int vl, int vr)
{
if(vl != vr)
{
sg[2 * v].mx = min(sg[v].mn, max(sg[v].mx, sg[2 * v].mx));
sg[2 * v + 1].mx = min(sg[v].mn, max(sg[v].mx, sg[2 * v + 1].mx));
sg[2 * v].mn = max(sg[v].mx, min(sg[v].mn, sg[2 * v].mn));
sg[2 * v + 1].mn = max(sg[v].mx, min(sg[v].mn, sg[2 * v + 1].mn));
sg[v].mn = 1e9;
sg[v].mx = 0;
}
}
void upd(int v, int vl, int vr, int l, int r, int val, int m)
{
if(vl > r || vr < l)
{
return;
}
push(v, vl, vr);
if(l <= vl && vr <= r)
{
if(m == 1)
{
sg[v].mx = max(sg[v].mx, val);
sg[v].mn = max(sg[v].mn, sg[v].mx);
}
else
{
sg[v].mn = min(sg[v].mn, val);
sg[v].mx = min(sg[v].mx, sg[v].mn);
}
push(v, vl, vr);
return;
}
int mid = (vl + vr) / 2;
upd(2 * v, vl, mid, l, r, val, m);
upd(2 * v + 1, mid + 1, vr, l, r, val, m);
}
query get(int v, int vl, int vr, int p)
{
if(vl > p || vr < p)
{
query tmp;
return tmp;
}
push(v, vl, vr);
if(vl == vr && vl == p)
{
return sg[v];
}
int mid = (vl + vr) / 2;
query lc = get(2 * v, vl, mid, p),
rc = get(2 * v + 1, mid + 1, vr, p);
query res; res.mn = min(lc.mn, rc.mn);
res.mx = max(lc.mx, rc.mx);
return res;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segment s;
for(int i = 0; i < k; i++)
{
s.upd(1, 0, MAXN - 1, left[i], right[i], height[i], op[i]);
}
for(int i = 0; i < n; i++)
{
query ans = s.get(1, 0, MAXN - 1, i);
finalHeight[i] = min(ans.mx, ans.mn);
}
}