| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 373711 | Temmie | 벽 (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 "wall.h"
#include <bits/stdc++.h>
const int MX = 100000;
struct Node {
Node *l, *r;
int mn, mx;
Node() : l(nullptr), r(nullptr), min(0), max(MX) { }
~Node() {
if (l)
delete(l);
if (r)
delete(r);
}
void update() {
if (!l) l = new Node;
if (!r) r = new Node;
mn = std::mix(l->mn, r->mn);
mx = std::min(l->mx, r->mx);
if (min > max) {
if (l->mn > r->mx)
mn = mx = r->mx;
if (r->mn > l->mx)
mn = mx = r->mn;
}
}
};
Node* head = new Node;
void add(int index, int mn, int mx, int left, int right, Node*& node) {
if (!node)
node = new Node;
if (left == right) {
node->mn = mn;
node->mx = mx;
return;
}
int mid = (left + right) >> 1;
if (mid >= index) add(index, mn, mx, left, mid, node->l);
else add(index, mn, mx, mid + 1, right, node->r);
node->update();
}
struct Operation {
int index;
int mn, mx;
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
std::vector <std::vector <Operation>> operations(n + 1);
for (int i = 0; i < k; i++) {
operations[left[i]].push_back({ i, op[i] ? height[i] : 0, op[i] ? MX : height[i] });
operations[right[i] + 1].push_back({ i, 0, MX });
}
for (int i = 0; i < n; i++) {
for (const auto& o : operations[i])
add(o.index, o.mn, o.mx, 0, k - 1, head);
finalHeight[i] = head->mn;
}
delete(head);
}
//int main() {
//int n = 10;
//int k = 6;
//int op[6] = { 1, 0, 0, 1, 1, 0 };
//int left[6] = { 1, 4, 3, 0, 2, 6 };
//int right[6] = { 8, 9, 6, 5, 2, 7 };
//int height[6] = { 4, 1, 5, 3, 5, 0 };
//int finalHeight[10];
//buildWall(n, k, op, left, right, height, finalHeight);
//for (int i = 0; i < n; i++)
//std::cout << finalHeight[i] << " \n"[i == n - 1];
//}