| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 860136 | promitheas | 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.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
template<typename T>
T max(T a, T b) {
return a < b ? b : a;
}
template<typename T>
T min(T a, T b) {
return a > b ? b : a;
}
template<typename T>
void minset(T& a, T b) {
a = min(a, b);
}
template<typename T>
void maxset(T& a, T b) {
a = max(a, b);
}
template<typename T>
void snap(T& a, T l, T h) {
minset(a, h);
maxset(a, l);
}
class Node {
public:
Node* left;
Node* right;
bool hasLazy = false;
int low;
int high;
void Propagate() {
if (!left)left = new Node(this);
if (!right)right = new Node(this);
snap(left->low, low, high);
snap(left->high, low, high);
snap(right->high, low, high);
snap(right->high, low, high);
}
Node* L() {
if (!left)left = new Node();
if (hasLazy) {
Propagate();
hasLazy = false;
}
return left;
}
Node* R() {
if (!right)right = new Node();
if (hasLazy) {
Propagate();
hasLazy = false;
}
return right;
}
Node(Node* par) : left{ nullptr }, right{ nullptr }, low{ par->low }, high{ par->high } {}
Node* L() {
return left ? left : left = new Node(this);
}
Node* R() {
return right ? right : right = new Node(this);
}
void BuildUp(int l, int r, int tl, int tr, int h) {
if (l == tl && r == tr) {
low = max(low, h); //bring lo to at least h
high = max(high, low); // hi must be at least lo
hasLazy = true;
return;
}
int mid = (l + r) >> 1;
if (tr <= mid) {
return L()->BuildUp(l, mid, tl, tr, h);
}
if (tl > mid) {
return R()->BuildUp(mid + 1, r, tl, tr, h);
}
L()->BuildUp(l, mid, tl, mid, h);
R()->BuildUp(mid + 1, r, mid + 1, tr, h);
}
void BreakDown(int l, int r, int tl, int tr, int h) {
if (l == tl && r == tr) {
high = min(high, h);
low = min(low, h);
hasLazy = true;
return;
}
int mid = (l + r) >> 1;
if (tr <= mid) {
return L()->BreakDown(l, mid, tl, tr, h);
}
if (tl > mid) {
return R()->BreakDown(mid + 1, r, tl, tr, h);
}
L()->BreakDown(l, mid, tl, mid, h);
R()->BreakDown(mid + 1, r, mid + 1, tr, h);
}
int GetVal(int l, int r, int t) {
if (l == r)
return low;
if (hasLazy) {
Propagate();
hasLazy = false;
}
int mid = (l + r) >> 1;
if (t <= mid)
return L()->GetVal(l, mid, t);
return R()->GetVal(mid + 1, r, t);
}
};
Node* node;
int N;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
node = new Node();
for (int i = 0; i < k; i++) {
if (op[i] == 1)
node->BuildUp(0, n - 1, left[i], right[i], height[i]);
else
node->BreakDown(0, n - 1, left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = node->GetVal(0, n - 1, i);
}
}