| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 714007 | iskhakkutbilim | 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>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e6;
struct info{
int mn, mx;
};
info tree[6*N];
int lazy[6*N], a[6*N];
int n, q;
info combine(info a, info b){
info res;
res.mx = max(a.mx, b.mx);
res.mn = min(a.mn, b.mn);
return res;
}
void build(int v, int vl, int vr){
lazy[v] = -1;
if(vl == vr){
tree[v] = {0, 0};
return;
}
int mid =(vl + vr)>>1;
build(v<<1, vl, mid);
build(v<<1|1, mid+1, vr);
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
}
void push(int v, int vl, int vr){
if(lazy[v] ==-1) return;
tree[v] = {lazy[v], lazy[v]};
if (vl == vr){
a[vl] = lazy[v];
}
if(vl != vr){
lazy[v<<1] = lazy[v];
lazy[v<<1|1] = lazy[v];
}
lazy[v] = -1;
}
void update(int l, int r, int x, int v, int vl, int vr){
push(v, vl, vr);
if(vl > r or l > vr) return;
if(l <= vl and r >= vr){
lazy[v] = x;
push(v, vl, vr);
return;
}
int mid =(vl + vr)>>1;
update(l, r, x, v<<1, vl, mid);
update(l, r, x, v<<1|1 , mid+1, vr);
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
}
int get(int pos, int v, int vl, int vr){
push(v, vl, vr);
if(vl == vr) return tree[v].mn;
int mid = (vl + vr)>>1;
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
if(mid >= pos) return get(pos, v<<1, vl, mid);
return get(pos, v<<1|1, mid+1, vr);
}
void max_equal(int l, int r, int x, int v, int vl, int vr){
push(v, vl, vr);
if(vl > r or l > vr) return;
if(tree[v].mn >= x){
return;
}
if(tree[v].mx < x){
update(l, r, x, v, vl, vr);
return;
}
if(vl == vr){
a[vl] = x;
tree[v] = {max(x, tree[v].mn), max(x, tree[v].mx)};
return;
}
int mid = (vl + vr)>>1;
max_equal(l, r, x, v<<1, vl, mid);
max_equal(l, r, x, v<<1|1, mid+1, vr);
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
}
void push_up(int v, int vl, int vr){
push(v, vl, vr);
if(vl == vr) return;
int mid =(vl + vr)>>1;
push_up(v<<1, vl, mid);
push_up(v<<1|1 , mid+1, vr);
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
}
void min_equal(int l, int r, int x, int v, int vl, int vr){
push(v, vl, vr);
if(vl > r or l > vr) return;
if(tree[v].mx <= x){
return;
}
if(tree[v].mn > x){
update(l, r, x, v, vl, vr);
return;
}
if(vl == vr){
a[vl] = x;
tree[v] = {max(x, tree[v].mn), max(x, tree[v].mx)};
return;
}
int mid = (vl + vr)>>1;
min_equal(l, r, x, v<<1, vl, mid);
min_equal(l, r, x, v<<1|1, mid+1, vr);
tree[v] = combine(tree[v<<1], tree[v<<1|1]);
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
build(1, 1, n);
while(q--){
int type; cin >> type;
int l, r, h; cin >> l >> r >> h;
l++, r++;
if(type ==1){
max_equal(l, r, h, 1, 1, n);
}else{
min_equal(l, r, h, 1, 1, n);
}
}
push_up(1, 1, n);
for(int i = 1;i <= n; i++) cout << a[i] << "\n";
return 0;
}