| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 657180 | 20060907 | Wall (IOI14_wall) | C++17 | 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>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0);
#define long long
#define vt vector
#define pb push_back
#define eb emplace_back
#define INF 0x3f3f3f3f
#define PI pair<int, int>
#define rep(i, from, to) for (int i = from; i <= to; i++)
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx,avx2,fma")
const int mxn = 2e6 + 5;
int n;
int tr[mxn << 2], add[mxn << 2], del[mxn << 2];
void push(int idx){
// cout << add[idx] << " " << del[idx] << "\n";
if(add[idx]){
if(add[idx] > add[idx << 1]){
add[idx << 1] = add[idx];
if(add[idx << 1] > del[idx << 1]) del[idx << 1] = add[idx << 1];
}
if(add[idx] > add[idx << 1 | 1]){
add[idx << 1 | 1] = add[idx];
if(add[idx << 1 | 1] > del[idx << 1 | 1]) del[idx << 1 | 1] = add[idx << 1 | 1];
}
add[idx] = 0;
}
if(del[idx] < INF){
if(del[idx] < del[idx << 1]){
del[idx << 1] = del[idx];
if(del[idx << 1] < add[idx << 1]) add[idx << 1] = del[idx << 1];
}
if(del[idx] < del[idx << 1 | 1]){
del[idx << 1 | 1] = del[idx];
if(del[idx << 1 | 1] < add[idx << 1 | 1]) add[idx << 1 | 1] = del[idx << 1 | 1];
}
del[idx] = INF;
}
}
// void push(int idx) {
// if (add[idx]) {
// cout << add[idx << 1] << ' ' << del[idx << 1] << ' ' << add[idx << 1 | 1] << ' ' << del[idx << 1 | 1] << '\n';
// add[idx << 1] = max(add[idx << 1], add[idx]);
// add[idx << 1 | 1] = max(add[idx << 1 | 1], add[idx]);
// del[idx << 1] = max(del[idx << 1], add[idx << 1]);
// del[idx << 1 | 1] = max(del[idx << 1], add[idx << 1 | 1]);
// add[idx] = 0;
// }
// if (del[idx] != INF) {
// cout << add[idx << 1] << ' ' << del[idx << 1] << ' ' << add[idx << 1 | 1] << ' ' << del[idx << 1 | 1] << '\n';
// del[idx << 1] = min(del[idx << 1], del[idx]);
// del[idx << 1 | 1] = min(del[idx << 1 | 1], del[idx]);
// add[idx << 1] = min(add[idx << 1], del[idx << 1]);
// add[idx << 1 | 1] = min(add[idx << 1 | 1], del[idx << 1 | 1]);
// del[idx] = INF;
// }
// cout << add[idx] << ' ' << del[idx] << '\n';
// }
int query(int pos, int idx = 1, int l = 1, int r = n) { //query(a, b, 1, 1, n);
if (l != r) push(idx);
else return add[idx];
int m = (l + r) >> 1;
if (pos > m) return query(pos, idx << 1 | 1, m + 1, r);
return query(pos, idx << 1, l, m);
// return combine(query(ql, qr, idx << 1, l, m), query(ql, qr, idx << 1 | 1, m + 1, r));
}
void ad(int ql, int qr, int v, int idx = 1, int l = 1, int r = n) { //update(ql, qr, value, 1, 1, n);
// cout << "ad " << l << ' ' << r << '\n';
if (l != r) push(idx);
if (ql <= l && qr >= r) {
add[idx] = max(add[idx], v);
del[idx] = max(del[idx], v);
return;
}
int m = (l + r) >> 1;
if (qr > m) ad(ql, qr, v, idx << 1 | 1, m + 1, r);
if (ql <= m) ad(ql, qr, v, idx << 1, l, m);
// tr[idx] = combine(tr[idx << 1], tr[idx << 1 | 1]);
}
void de(int ql, int qr, int v, int idx = 1, int l = 1, int r = n) { //update(ql, qr, value, 1, 1, n);
// cout << "de " << l << ' ' << r << '\n';
if (l != r) push(idx);
if (ql <= l && qr >= r) {
add[idx] = min(add[idx], v);
del[idx] = min(del[idx], v);
return;
}
int m = (l + r) >> 1;
if (qr > m) de(ql, qr, v, idx << 1 | 1, m + 1, r);
if (ql <= m) de(ql, qr, v, idx << 1, l, m);
// tr[idx] = combine(tr[idx << 1], tr[idx << 1 | 1]);
}
signed main(void){
fio
memset(del, 0x3f, sizeof(del));
int q, cmd, l, r, h;
cin >> n >> q;
while (q--) {
cin >> cmd >> l >> r >> h;
++l; ++r;
if (cmd == 1) ad(l, r, h);
else de(l, r, h);
// cout << '\n';
}
rep(i, 1, n) cout << query(i) << ' ';
cout << '\n';
}