| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1199983 | Richard_Dyinman | Wall (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define file \
freopen("haybales.in", "r", stdin);\
freopen("haybales.out", "w", stdout)
#define OJudge(in,out) \
freopen(in, "r", stdin);\
freopen(out, "w", stdout)
#define FIn \
cin.tie(0); \
cout.tie(0); \
ios_base::sync_with_stdio(false)
const string IN = "input.txt";
const string OUT = "output.txt";
int tc;
struct no{
ll add = 0, rem = 0, set = -1;
};
struct seg_tree{
vector<ll>tree;
vector<no> lazy;
int size;
void init(int n){
size = 1;
while(size < n)
size *=2;
tree.resize(2*size + 5, 0ll);
lazy.resize(2*size + 5);
}
void set(int idx, ll val, int l, int r, int node){
// if(l == r){
// return;
// }
// int mid = (l + r)/2;
// if(idx <= mid)
// set(idx, val, l , mid, 2*node);
// else
// set(idx, val, mid + 1, r, 2*node + 1);
// tree[node].s = (tree[2*node].s + tree[2*node + 1].s);
// tree[node].pref = max(tree[2*node].pref , tree[2*node].s + tree[2*node + 1].pref);
}
void set(int idx, ll val){
set(idx , val, 1, size , 1);
}
void push(int l, int r, int node){
if(r - l){
if (lazy[node].set != -1) {
lazy[2 * node].set = lazy[node].set;
lazy[2 * node + 1].set = lazy[node].set;
lazy[2 * node].add = 0;
lazy[2 * node + 1].add = 0;
lazy[2 * node].rem = 0;
lazy[2 * node + 1].rem = 0;
} else if (lazy[node].add != 0) {
if (lazy[2 * node].set != -1) {
lazy[2 * node].set = max(lazy[2 * node].set, lazy[node].add);
lazy[2 * node].add = 0;
lazy[2 * node].rem = 0;
} else {
if (lazy[2 * node].rem < lazy[node].add) {
lazy[2 * node].set = lazy[node].add;
lazy[2 * node].add = 0;
lazy[2 * node].rem = 0;
} else {
lazy[2 * node].add = max(lazy[node].add, lazy[2 * node].add);
}
}
if (lazy[2 * node + 1].set != -1) {
lazy[2 * node + 1].set = max(lazy[2 * node + 1].set, lazy[node].add);
lazy[2 * node + 1].add = 0;
lazy[2 * node + 1].rem = 0;
} else {
if (lazy[2 * node + 1].rem < lazy[node].add) {
lazy[2 * node + 1].set = lazy[node].add;
lazy[2 * node + 1].add = 0;
lazy[2 * node + 1].rem = 0;
} else {
lazy[2 * node + 1].add = max(lazy[node].add, lazy[2 * node + 1].add);
}
}
} else if (lazy[node].rem != 0) {
if (lazy[2 * node].set != -1) {
lazy[2 * node].set = min(lazy[2 * node].set, lazy[node].rem);
lazy[2 * node].add = 0;
lazy[2 * node].rem = 0;
} else {
if (lazy[2 * node].add > lazy[node].rem) {
lazy[2 * node].set = lazy[node].rem;
lazy[2 * node].add = 0;
lazy[2 * node].rem = 0;
} else {
lazy[2 * node].rem = min(lazy[node].rem, lazy[2 * node].rem);
}
}
if (lazy[2 * node + 1].set != -1) {
lazy[2 * node + 1].set = min(lazy[2 * node + 1].set, lazy[node].rem);
lazy[2 * node + 1].add = 0;
lazy[2 * node + 1].rem = 0;
} else {
if (lazy[2 * node + 1].add > lazy[node].rem) {
lazy[2 * node + 1].set = lazy[node].rem;
lazy[2 * node + 1].add = 0;
lazy[2 * node + 1].rem = 0;
} else {
lazy[2 * node + 1].rem = min(lazy[node].rem, lazy[2 * node + 1].rem);
}
}
}
}else{
if(lazy[node].set != -1){
tree[node] = lazy[node].set;
}else{
tree[node] = max(lazy[node].add , lazy[node].rem);
}
}
no s;
lazy[node] = s;
}
void add(int l1, int r1, ll val, int l, int r, int node){
push(l , r, node);
if(r < l1 || l > r1)
return;
if(l >= l1 && r <= r1){
lazy[node].add = val;
push(l , r, node);
return;
}
int mid = (l + r)/2;
add(l1 , r1, val, l, mid, node*2);
add(l1 , r1, val, mid + 1, r, 2*node + 1);
}
void add(int l, int r , ll val){
add(l , r, val, 1 , size , 1);
}
void rem(int l1, int r1, ll val, int l, int r, int node){
push(l , r, node);
if(r < l1 || l > r1)
return;
if(l >= l1 && r <= r1){
lazy[node].rem = val;
push(l , r, node);
return;
}
int mid = (l + r)/2;
rem(l1 , r1, val, l, mid, node*2);
rem(l1 , r1, val, mid + 1, r, 2*node + 1);
}
void rem(int l, int r, ll val){
rem(l , r, val , 1, size, 1);
}
ll get(int idx, int l, int r, int node){
push(l , r, node);
if(l == r){
return tree[node];
}
int mid = (l + r)/2;
if(idx <= mid)
return get(idx , l, mid, 2*node);
return get(idx, mid + 1, r, 1 + 2*node);
}
ll get(int idx){
return get(idx, 1, size, 1);
}
};
ll n, m, a, b, c,d, k;
void solve(){
cin>>n>>m;
seg_tree sg;
sg.init(n);
// for(int i = 1; i <= n; i++){
// cin>>a;
// sg.set(i , a);
// }
while(m--){
cin>>a;
if(a == 1){
cin>>a>>b>>c;
a++,b++;
sg.add(a , b , c);
}else{
cin>>a>>b>>c;
a++,b++;
sg.rem(a , b,c);
}
}
for(int i = 1; i <= n; i++){
cout<<sg.get(i)<<" ";
}
}
int main() {
FIn;
// file;
// #ifndef ONLINE_JUDGE
// OJudge(IN.c_str(),OUT.c_str());
// #endif
bool test = 0;
if (test)
cin>>tc;
else tc = 1;
for (int i = 1; i<=tc; i++){
solve();
}
}