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>
using namespace std;
#define lc (id << 1)
#define rc (lc | 1)
typedef long long ll;
int const N = 1e5 + 5;
int seg[N << 2][2];
inline void apply(int mn, int mx, int res[2]) {
for (int i : {0, 1})
res[i] = min(mx, max(mn, res[i]));
}
inline void shift(int id) {
apply(seg[id][0], seg[id][1], seg[lc]);
apply(seg[id][0], seg[id][1], seg[rc]);
seg[id][0] = 0;
seg[id][1] = INT_MAX;
}
void build(int id, int l, int r) {
if (r - l == 1) {
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid); build(rc, mid, r);
seg[id][1] = INT_MAX;
}
void update(int id, int l, int r, int ql, int qr, int mn, int mx) {
if (qr <= l || r <= ql)
return;
if (ql <= l && r <= qr)
return apply(mn, mx, seg[id]);
shift(id);
int mid = (l + r) >> 1;
update(lc, l, mid, ql, qr, mn, mx);
update(rc, mid, r, ql, qr, mn, mx);
}
void finish(int id, int l, int r, int arr[]) {
if (r - l == 1) {
arr[l] = seg[id][0];
return;
}
shift(id);
int mid = (l + r) >> 1;
finish(lc, l, mid, arr);
finish(rc, mid, r, arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 0, n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
update(1, 0, n, left[i], right[i] + 1, height[i], INT_MAX);
}
else {
update(1, 0, n, left[i], right[i] + 1, 0, height[i]);
}
}
finish(1, 0, n, finalHeight);
return;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |