| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 411402 | jhwest2 | Wall (IOI14_wall) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 2e6 + 10;
const int INF = 1e9 + 10;
int n, k, A[M];
struct SEG {
int T[M << 2][2], L[M << 2][2];
void init(int lo = 1, int hi = n, int idx = 1) {
L[idx][0] = L[idx][1] = INF;
if (lo == hi) return;
init(lo, lo + hi >> 1, idx << 1);
init(1 + (lo + hi >> 1), hi, idx << 1 | 1);
}
void push(int lo, int hi, int idx) {
for (int j = 0; j < 2; j++) {
int x = L[idx][j];
if (x == INF) continue;
if (x > 0) T[idx][j] = max(T[idx][j], x);
else T[idx][j] = min(T[idx][j], -x);
if (lo != hi) {
for (int i = idx << 1; i <= (idx << 1 | 1); i++) {
if (L[i][j] == INF) L[i][j] = x;
else if (x > 0 && L[i][j] <= 0 && -L[i][j] < x) {
if (T[i][j] >= x) L[i][j] = -x;
else L[i][j] = x;
}
else if (x <= 0 && L[i][j] > 0 && -x < L[i][j]) {
if (T[i][j] <= -x) L[i][j] = -x;
else L[i][j] = x;
}
else L[i][j] = max(L[i][j], x);
}
}
L[idx][j] = INF;
}
}
void update(int a, int b, int x, int lo = 1, int hi = n, int idx = 1) {
push(lo, hi, idx);
if (b < lo || a > hi) return;
if (a <= lo && hi <= b) {
L[idx][0] = L[idx][1] = x; push(lo, hi, idx); return;
}
update(a, b, x, lo, lo + hi >> 1, idx << 1);
update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
T[idx][0] = min(T[idx << 1][0], T[idx << 1 | 1][0]);
T[idx][1] = max(T[idx << 1][1], T[idx << 1 | 1][1]);
}
int query(int a, int lo = 1, int hi = n, int idx = 1) {
push(lo, hi, idx);
if (lo == hi) return T[idx][0];
if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
}
} S;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> k; S.init();
for (int i = 1; i <= k; i++) {
int op, l, r, h;
cin >> op >> l >> r >> h; ++l; ++r;
if (op == 1 && h != 0) S.update(l, r, h);
if (op == 2) S.update(l, r, -h);
}
for (int i = 1; i <= n; i++) {
cout << S.query(i) << '\n';
}
}