| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1111097 | TheGreatAntivirus | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "wall.h"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define stdI freopen("input.txt", "r", stdin);
#define stdO freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define mp(x, y) make_pair(x, y)
#define int long long
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
template<typename T, template<typename> class order = less>
using ordered_set = tree<T,
null_type, order<T>, rb_tree_tag,
tree_order_statistics_node_update>;
typedef pair<int, int> pii;
const int MAXN = (1 << 21), MAXLOG = 18, MAXSQ = 500, INF = 1e9, MOD = 1e9 + 7;
struct query
{
int mx, mn;
query()
{
mx = 0; mn = INF;
}
};
query sg[2 * MAXN];
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);
}
}