| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 416843 | DEQK | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 2e6 + 11;
int kp[N * 4];
int mn[N * 4], mx[N * 4];
void push(int u) {
if(kp[u] == -1) return;
mn[ls] = mn[rs] = kp[u];
mx[ls] = mx[rs] = kp[u];
kp[ls] = kp[rs] = kp[u];
kp[u] = -1;
}
void add(int ql,int qr,int x,int u,int l,int r) {
if(ql > r || l > qr || mn[u] >= x) return;
if(ql <= l && r <= qr) {
if(mx[u] <= x) {
kp[u] = x;
return;
}
}
push(u);
int m = l + r >> 1;
add(ql, qr, x, ls, l, m);
add(ql, qr, x, rs, m + 1, r);
mn[u] = min(mn[ls], mn[rs]);
mx[u] = max(mx[ls], mx[rs]);
}
void del(int ql,int qr,int x,int u,int l,int r) {
if(ql > r || l > qr || mx[u] <= x) return;
if(ql <= l && r <= qr) {
if(mn[u] >= x) {
kp[u] = x;
return;
}
}
push(u);
int m = l + r >> 1;
del(ql, qr, x, ls, l, m);
del(ql, qr, x, rs, m + 1, r);
mn[u] = min(mn[ls], mn[rs]);
mx[u] = max(mx[ls], mx[rs]);
}
int get(int p,int u,int l,int r) {
if(l == r) {
return mn[u];
}
push(u);
int m = l + r >> 1;
if(p <= m) return get(p, ls, l, m);
else return get(p, rs, m + 1, r);
}
void buildWall(int n,int k, vector<int> op, vector<int> left, vector<int> right, vector<int> height, vector<int> finalHeight) {
memset(kp, -1, sizeof(kp));
for(int i = 0; i < k; i++) {
int l = left[i], r = right[i], type = op[i], x = op[i];
if(type == 1) {
add(l, r, x, 1, 0, n - 1);
} else {
del(l, r, x, 1, 0, n - 1);
}
}
for(int i = 0; i < n; i++) {
finalHeight[i] = get(i, 1, 0, n - 1);
}
}