| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209849 | jonteo_2001 | Wall (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#pragma once
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define ll long long
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
using namespace std;
struct ops {
int type, val;
ops(int type, int val): type(type), val(val){}
};
class SegTree {
public:
vector<int> t;
vector<deque<ops>> lazy;
SegTree(int n){
t = vector<int> (4*n);
lazy = vector<deque<ops>>(4*n, deque<ops>());
}
void apply(int v, int tl, int tr, deque<ops> above_ops){
while (!above_ops.empty()){
ops op = above_ops.front(); above_ops.pop_front();
// cerr << "op = " << op.type << ", " << op.val << endl;
// combine with any below ops as far as possible
while (!lazy[v].empty()){
ops last = lazy[v].back();
// cerr << "last.type = " << last.type<<endl;
if (last.type == 0 || op.type == 0){
if (last.type == 0){
switch (op.type){
case 1: op.val = max(op.val, last.val); break;
case 2: op.val = min(op.val, last.val); break;
default: break;
}
}
// lazy[v].clear();
op.type = 0;
break;
}
// Case 1: types are the same
if (last.type == op.type){
if (last.type == 1){
op.val = max(op.val,last.val);
} else if (last.type == 2){
op.val = min(op.val,last.val);
} else assert(false);
lazy[v].pop_back();
} else {
// one min, one max and if the values are the same, just break.
if (last.val == op.val){
// lazy[v].clear();
op.type = 0;
break;
}
if (last.type == 1 && op.type == 2){
// last = max, op = min
if (op.val < last.val){
// lazy[v].pop_back();
op.type = 0;
break;
} else {
// cannot combine
break;
}
} else {
// last = min, op = max
if (op.val > last.val){
op.type = 0;
break;
// lazy[v].pop_back();
} else{
// cannot combine
break;
}
}
}
}
if (op.type == 0){
lazy[v].clear();
}
lazy[v].push_back(op);
}
// cerr << "***********" << endl;
}
void prop(int v, int tl, int tr){
if (tl == tr) {
while (!lazy[v].empty()){
ops cur_op = lazy[v].front();
lazy[v].pop_front();
switch (cur_op.type){
case 0: t[v] = cur_op.val; break;
case 1: t[v] = max(t[v], cur_op.val); break;
case 2: t[v] = min(t[v], cur_op.val); break;
default: assert(false);
}
}
return;
}
int tm = (tl + tr) / 2;
apply(v*2, tl, tm, lazy[v]);
apply(v*2+1, tm+1, tr, lazy[v]);
lazy[v].clear();
}
void update(int v, int tl, int tr, int l, int r, ops op){
if (r < tl || tr < l) return;
if (l <= tl && tr <= r){
deque<ops> cur_ops; cur_ops.push_back(op);
apply(v, tl, tr, cur_ops);
} else{
prop(v, tl, tr);
int tm = (tl + tr) / 2;
update(v*2, tl, tm, l, r, op);
update(v*2+1, tm+1, tr, l, r, op);
}
}
void query(int v, int tl, int tr, vector<int>& a){
prop(v, tl, tr);
if (tl == tr){
a[tl] = t[v];
return;
}
int tm = (tl + tr) / 2;
query(v*2, tl, tm, a);
query(v*2+1, tm+1, tr, a);
}
};
// Write implementation prototypes Here
void buildWall(int n, int k, vector<int>& op, vector<int>& left, vector<int>& right, vector<int>& height, vector<int>& finalHeight){
// PRINT THE ANSWER!
// finalHeight.resize(n);
SegTree st = SegTree(n);
for (int i = 0; i < k; ++i){
ops cur = ops(op[i], height[i]);
st.update(1, 0, n-1, left[i], right[i], cur);
// st.query(1, 0, n-1, finalHeight);
}
st.query(1, 0, n-1, finalHeight);
}
// Driver code
// int main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// if (fopen("test.inp", "r") != NULL) {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// freopen("test.err", "w", stderr);
// }
// int n, k; cin >> n >> k;
// vector<int> op(k), left(k), right(k), height(k);
// for (int i = 0; i < k; ++i){
// cin >> op[i] >> left[i] >> right[i] >> height[i];
// }
// vector<int> finalHeight(n);
// buildWall(n, k, op, left, right, height, finalHeight);
// for (auto it: finalHeight){
// cout << it << " ";
// }
// cout << endl;
// return 0;
// }