| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1138595 | Ekber_Ekber | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
using namespace std;
struct point{
int ma, mi;
};
int ctoi(char x) {
return (int)x - '0';
}
int sumab(int a, int b) {
return (a + b) * (b - a + 1) / 2;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
void print(vector <int> &v) {
for (const int &i : v) cout << i << ' ';
}
constexpr int MAX = 2e+6 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);
vector <point> t(4 * MAX, {0, 0}), lazy(4 * MAX, {-1, INF});
vector <int> h;
void push(int v) {
if (lazy[v].ma != -1) {
if (t[v*2].mi < lazy[v].ma) {
t[v*2].mi = lazy[v].ma;
t[v*2].ma = max(t[v*2].ma, t[v*2].mi);
lazy[v*2].ma = max(lazy[v*2].ma, lazy[v].ma);
}
if (t[v*2+1].mi < lazy[v].ma) {
t[v*2+1].mi = lazy[v].ma;
t[v*2+1].ma = max(t[v*2+1].ma, t[v*2+1].mi);
lazy[v*2+1].ma = max(lazy[v*2+1].ma, lazy[v].ma);
}
lazy[v].ma = -1;
}
if (lazy[v].mi != INF) {
if (t[v*2].ma > lazy[v].mi) {
t[v*2].ma = lazy[v].mi;
t[v*2].mi = min(t[v*2].mi, t[v*2].ma);
lazy[v*2].mi = min(lazy[v*2].mi, lazy[v].mi);
}
if (t[v*2+1].ma > lazy[v].mi) {
t[v*2+1].ma = lazy[v].mi;
t[v*2+1].mi = min(t[v*2+1].mi, t[v*2+1].ma);
lazy[v*2+1].mi = min(lazy[v*2+1].mi, lazy[v].mi);
}
lazy[v].mi = INF;
}
}
void update1(int v, int tl, int tr, int l, int r, int x) { // increase
if (l > r) return;
if (tl == l && tr == r) {
if (t[v].mi < x) {
lazy[v].ma = max(lazy[v].ma, x);
if (lazy[v].mi < lazy[v].ma) {
lazy[v].mi = lazy[v*2].mi = lazy[v*2+1].mi = INF;
}
t[v].mi = x;
t[v].ma = max(t[v].ma, t[v].mi);
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update1(v*2, tl, tm, l, min(r, tm), x);
update1(v*2+1, tm+1, tr, max(l, tm+1), r, x);
t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}
void update2(int v, int tl, int tr, int l, int r, int x) { // decrease
if (l > r) return;
if (tl == l && tr == r) {
if (t[v].ma > x) {
lazy[v].mi = min(lazy[v].mi, x);
if (lazy[v].mi < lazy[v].ma) {
lazy[v].ma = lazy[v*2].ma = lazy[v*2+1].ma = -1;
}
t[v].ma = x;
t[v].mi = max(t[v].ma, t[v].mi);
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update2(v*2, tl, tm, l, min(r, tm), x);
update2(v*2+1, tm+1, tr, max(l, tm+1), r, x);
t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
h.pb(t[v].ma);
return;
}
push(v);
int tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int z=0; z < k; z++) {
if (op[z] == 1) {
update1(1, 0, n-1, left[z], right[z], height[z]);
}
else {
update2(1, 0, n-1, left[z], right[z], height[z]);
}
}
build(1, 0, n-1);
for (int i=0; i < n; i++) {
finalHeight[i] = h[i];
}
return;
}
void _() {
int n, k;
cin >> n >> k;
int l[k], r[k], a[k], h[k];
for (int i=0; i < k; i++) {
cin >> a[i] >> l[i] >> r[i] >> h[i];
}
int res[n];
buildWall(n, k, a, l, r, h, res);
for (int i=0; i < n; i++) cout << res[i] << ' ';
}
signed main() {
GOOD_LUCK
int tests=1;
// cin >> tests;
while (tests--) {
_();
// cout << endl;
}
return 0;
}
// Problem X
// by Ekber_Ekber