| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1106592 | YudoTLE | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vb = vector<bool>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
struct Query
{
int type, height;
};
template <typename T>
struct LazySegmentTree
{
int sz;
vector<T> tseg;
vector<Query> tlazy;
LazySegmentTree(int sz)
: sz(sz), tseg(sz * 4), tlazy(sz * 4)
{}
T _combine(T vl, T vr)
{
return vl + vr;
}
void _apply(int tl, int tr, int t, Query q)
{
if (q.type == 1)
{
if (tlazy[t].type == 0)
{
tseg[t] = max(tseg[t], q.height);
tlazy[t] = q;
}
if (tlazy[t].type == 1)
{
if (tlazy[t].height > q.height)
return;
tseg[t] = q.height;
tlazy[t] = q;
}
if (tlazy[t].type == 2)
{
tseg[t] = max(tseg[t], tlazy[t].height);
tlazy[t] = {
q.type,
max(tlazy[t].height, q.height)
};
}
}
if (q.type == 2)
{
if (tlazy[t].type == 0)
{
tseg[t] = min(tseg[t], q.height);
tlazy[t] = q;
}
if (tlazy[t].type == 1)
{
tseg[t] = min(tseg[t], tlazy[t].height);
tlazy[t] = {
q.type,
min(tlazy[t].height, q.height)
};
}
if (tlazy[t].type == 2)
{
if (tlazy[t].height < q.height)
return;
tseg[t] = q.height;
tlazy[t] = q;
}
}
}
void _push_down(int tl, int tr, int t)
{
int tm = tl + (tr - tl) / 2;
_apply(tl, tm, t * 2 + 1, tlazy[t]);
_apply(tm + 1, tr, t * 2 + 2, tlazy[t]);
tlazy[t] = {0, 0};
}
void update(int l, int r, Query q, int tl=0, int tr=-1, int t=0)
{
if (tr == -1) tr += sz;
if (tr < l || r < tl)
return;
if (l <= tl && tr <= r)
{
_apply(tl, tr, t, q);
return;
}
_push_down(tl, tr, t);
int tm = tl + (tr - tl) / 2;
update(l, r, q, tl, tm, t * 2 + 1);
update(l, r, q, tm + 1, tr, t * 2 + 2);
tseg[t] = _combine(tseg[t * 2 + 1], tseg[t * 2 + 2]);
}
T query(int i, int tl=0, int tr=-1, int t=0)
{
if (tr == -1) tr += sz;
if (tr < i || i < tl)
return 0;
if (tl == tr)
return tseg[t];
_push_down(tl, tr, t);
int tm = tl + (tr - tl) / 2;
if (i <= tm)
return query(i, tl, tm, t * 2 + 1);
else
return query(i, tm + 1, tr, t * 2 + 2);
}
};
void solve()
{
int n, q;
cin >> n >> q;
LazySegmentTree<int> st(n + 1);
while (q--)
{
int op, l, r, h;
cin >> op >> l >> r >> h;
st.update(l, r, Query{op, h});
}
vi ans(n + 1);
for (int i = 1; i <= n; i++)
ans[i] = st.query(i);
for (int i = 1; i <= n; i++)
cout << ans[i] << " \n"[i==n];
}
int main()
{
// ios_base::sync_with_stdio(false), cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}