| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1266905 | ngocphu | 벽 (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 2000000000000000000LL;
const int maxN = 2e6 + 4;
const int LOG = 18;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
const int MOD = 1e9 + 7;
const int base = 311;
int n, k;
struct dataa
{
int min_val, max_val;
dataa()
{
min_val = 0;
max_val = 1e9;
}
dataa(int a, int b)
{
min_val = a;
max_val = b;
}
};
dataa st[4 * maxN];
void apply(int id, dataa x)
{
st[id].min_val = max(st[id].min_val, x.min_val);
st[id].max_val = max(st[id].max_val, st[id].min_val);
st[id].max_val = min(st[id].max_val, x.max_val);
st[id].min_val = min(st[id].min_val, st[id].max_val);
}
void push(int id)
{
apply(id * 2, st[id]);
apply(id * 2 + 1, st[id]);
st[id] = dataa(0, 1e9);
}
void update(int id, int l, int r, int u, int v, dataa x)
{
if (l > v || r < u) return;
if (l >= u && r <= v) apply(id, x);
else
{
push(id);
int m = (l + r) / 2;
update(id * 2, l, m, u, v, x);
update(id * 2 + 1, m + 1, r, u, v, x);
}
}
dataa get(int id, int l, int r, int idx)
{
if (l == r)
{
return st[id];
}
else
{
push(id);
int m = (l + r) / 2;
if (idx <= m) return get(id * 2, l, m, idx);
else return get(id * 2 + 1, m + 1, r, idx);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// freopen(".INP","r",stdin);
// freopen(".OUT","w",stdout);
cin >> n >> k;
for (int i = 1; i <= k; ++i)
{
int t, l, r, h; cin >> t >> l >> r >> h;
l++;r++;
if (t == 1) update(1, 1, n, l, r, dataa(h, 1e9));
else update(1, 1, n, l, r, dataa(0, h));
}
for (int i = 1; i <= n; ++i) cout << get(1, 1, n, i).min_val << " ";
return 0;
}