| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 337889 | Azimjon | 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 <bits/stdc++.h>
#include "wall.h"
const int INF = 1e9;
const int N = 2e6 + 10;
int ka[N], ki[N], ish[N];
int* a;
int n;
bool ha = 0;
void minim(int, int, int, int, int, int);
void maxim(int, int, int, int, int, int);
void init() {
for (int i = 0; i < N; i++) {
ka[i] = 0;
ki[i] = INF;
}
}
void minim(int v, int l, int r, int tl, int tr, int h) {
if (r < tl || tr < l) return;
if (tl <= l && r <= tr) {
ki[v] = min(ki[v], h);
ka[v] = min(ka[v], ki[v]);
ish[v] = 1;
return;
}
int m = (l + r) / 2;
if (ish[v]) {
ish[v] = 0;
ish[2 * v] = ish[2 * v + 1] = 1;
maxim(2 * v, l, m, l, m, ka[v]);
minim(2 * v, l, m, l, m, ki[v]);
maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
}
minim(2 * v, l, m, tl, tr, h);
minim(2 * v + 1, m + 1, r, tl, tr, h);
}
void maxim(int v, int l, int r, int tl, int tr, int h) {
if (tr < l || r < tl) return;
if (tl <= l && r <= tr) {
ka[v] = max(ka[v], h);
ki[v] = max(ki[v], ka[v]);
ish[v] = 1;
return;
}
// cout << __LINE__ << endl;
int m = (l + r) / 2;
if (ish[v]) {
ish[v] = 0;
ish[2 * v] = ish[2 * v + 1] = 1;
minim(2 * v, l, m, l, m, ki[v]);
maxim(2 * v, l, m, l, m, ka[v]);
minim(2 * v + 1, m + 1, r, m + 1, r, ki[v]);
maxim(2 * v + 1, m + 1, r, m + 1, r, ka[v]);
}
maxim(2 * v, l, m, tl, tr, h);
maxim(2 * v + 1, m + 1, r, tl, tr, h);
}
int get(int v, int l, int r, int x) {
// if (x < l || r < x) return -1;
if (l == r) {
return ka[v];
}
int m = (l + r) / 2;
if (x <= m)
return get(2 * v, l, m, x);
else
return get(2 * v + 1, m + 1, r, x);
}
void buildWall(int nn, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
n = nn;
init();
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
maxim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
// cout << "Maxim succesfull" << endl;
} else {
ha = 1;
minim(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
ha = 0;
// cout << "Minim succesfull" << endl;
}
/*for (int i = 1; i <= n; i++) {
minim(1, 1, n, i, i, INF);
maxim(1, 1, n, i, i, 0);
cout << get(1, 1, n, i) << " ";
}
cout << endl;*/
}
for (int i = 1; i <= n; i++) {
minim(1, 1, n, i, i, INF);
maxim(1, 1, n, i, i, 0);
finalHeight[i - 1] = get(1, 1, n, i);
}
return;
}