| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 612191 | nohaxjustsoflo | 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 <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxN = 2 * 1e5;
struct node
{
int min, max, add, destruct;
};
struct segmentTree
{
int size;
vector<node> val;
void build(int n, int index, int Lx, int Rx)
{
if(Rx - Lx == 1)
{
if(Lx < n)
{
val[index] = {0, 0, -1, -1};
}
else
{
val[index] = {INT_MAX, -INT_MAX, -1, -1};
}
}
else
{
int m = (Lx + Rx) / 2;
build(n, index * 2 + 1, Lx, m);
build(n, index * 2 + 2, m, Rx);
val[index] = {0, 0, -1, -1};
}
}
void build(int n)
{
size = 1;
while(size < n) size <<= 1;
val = vector<node>(size * 2);
build(n, 0, 0, size);
}
void add(int index, int h)
{
val[index].min = max(val[index].add, h);
val[index].add = val[index].min;
val[index].max = max(val[index].max, val[index].min);
if(val[index].destruct != -1)
{
val[index].destruct = max(val[index].destruct, val[index].add);
}
}
void destruct(int index, int h)
{
if(val[index].destruct != -1)
{
val[index].max = min(val[index].destruct, h);
}
else
{
val[index].max = h;
}
val[index].destruct = val[index].max;
val[index].min = min(val[index].min, val[index].max);
if(val[index].add != -1)
{
val[index].add = min(val[index].add, val[index].destruct);
}
}
node func(node left, node right)
{
return {min(left.min, right.min), max(left.max, right.max), -1, -1};
}
void add(int l, int r, int h, int index, int Lx, int Rx)
{
if(Rx <= l || Lx >= r) return;
if(Lx >= l && Rx <= r)
{
add(index, h);
return;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
int m = (Rx + Lx) / 2;
add(l, r, h, index * 2 + 1, Lx, m);
add(l, r, h, index * 2 + 2, m, Rx);
val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
}
void add(int l, int r, int h)
{
add(l, r, h, 0, 0, size);
}
void destruct(int l, int r, int h, int index, int Lx, int Rx)
{
if(Rx <= l || Lx >= r) return;
if(Lx >= l && Rx <= r)
{
destruct(index, h);
return;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
int m = (Rx + Lx) / 2;
destruct(l, r, h, index * 2 + 1, Lx, m);
destruct(l, r, h, index * 2 + 2, m, Rx);
val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
}
void destruct(int l, int r, int h)
{
destruct(l, r, h, 0, 0, size);
}
void print(int n, int index, int Lx, int Rx)
{
if(Rx - Lx == 1)
{
if(Lx < n)
{
cout << val[index].min << "\n";
}
return;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
if(val[index].min == val[index].max && val[index].min != -1)
{
for(int i = 0; i < Rx - Lx; i++)
{
if(Lx + i < n)
{
cout << val[index].min << "\n";
}
else
{
break;
}
}
return;
}
int m = (Rx + Lx) / 2;
print(n, index * 2 + 1, Lx, m);
print(n, index * 2 + 2, m, Rx);
}
void print(int n)
{
print(n, 0, 0, size);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
segmentTree st;
st.build(n);
while(k--)
{
int op, l, r, h;
cin >> op >> l >> r >> h;
r++;
if(op == 1)
{
st.add(l, r, h);
}
else
{
st.destruct(l, r, h);
}
}
st.print(n);
}