| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1276695 | turral | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
#include "wall.h"
#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int INF = 1e18;
int log2_ceil(int n){
return 63 - __builtin_clzll(n) + (__builtin_popcount(n) != 1);
}
inline int L(int node){
return 2*node;
}
inline int R(int node){
return 2*node + 1;
}
struct segment_tree {
int numElements, N;
vector<int> stMax, stMin;
vector<bool> lazyAdd, lazyRemove;
segment_tree(int _numEl) : numElements(_numEl) {
N = (1 << log2_ceil(numElements));
stMax.assign(2*N, -INF);
stMin.assign(2*N, INF);
lazyAdd.assign(2*N, false);
lazyRemove.assign(2*N, false);
for (int i=0; i<numElements; ++i) stMax[i+N] = stMin[i+N] = 0;
for (int i=N-1; i>=1; --i) stMin[i] = min(stMin[L(i)], stMin[R(i)]);
for (int i=N-1; i>=1; --i) stMax[i] = max(stMax[L(i)], stMax[R(i)]);
}
void addLazyFunc(int node, int h){
if (stMin[node] >= h) return;
stMin[node] = h;
lazyAdd[node] = true;
if (stMax[node] < h){
stMax[node] = h;
lazyRemove[node] = true;
}
}
void removeLazyFunc(int node, int h){
if (stMax[node] <= h) return;
stMax[node] = h;
lazyRemove[node] = true;
if (stMin[node] > h){
stMin[node] = h;
lazyAdd[node] = true;
}
}
void pushAdd(int node){
if (node < N){
addLazyFunc(L(node), stMin[node]);
addLazyFunc(R(node), stMin[node]);
}
lazyAdd[node] = false;
}
void pushRemove(int node){
if (node < N){
removeLazyFunc(L(node), stMax[node]);
removeLazyFunc(R(node), stMax[node]);
}
lazyRemove[node] = false;
}
void push(int node){
if (lazyAdd[node]) pushAdd(node);
if (lazyRemove[node]) pushRemove(node);
}
void remove(int node, int l, int r, int a, int b, int h){
if (b < l || r < a) return;
if (a <= l && r <= b){
removeLazyFunc(node, h);
return;
}
push(node);
int m = (l+r)/2;
remove(L(node), l, m, a, b, h);
remove(R(node), m+1, r, a, b, h);
stMin[node] = min(stMin[L(node)], stMin[R(node)]);
stMax[node] = max(stMax[L(node)], stMax[R(node)]);
}
void remove(int a, int b, int h){
remove(1, 0, N-1, a, b, h);
}
void add(int node, int l, int r, int a, int b, int h){
if (b < l || r < a) return;
if (a <= l && r <= b){
addLazyFunc(node, h);
return;
}
push(node);
int m = (l+r)/2;
add(L(node), l, m, a, b, h);
add(R(node), m+1, r, a, b, h);
stMin[node] = min(stMin[L(node)], stMin[R(node)]);
stMax[node] = max(stMax[L(node)], stMax[R(node)]);
}
void add(int a, int b, int h){
add(1, 0, N-1, a, b, h);
}
vector<int> getState(){
vector<int> res(numElements);
for (int i=1; i<N; ++i) push(i);
for (int i=0; i<numElements; ++i) res[i] = stMin[i+N];
return res;
}
};
void buildWall(int n, int k, int * op[], int * left[], int * right[], int * height[], int * finalHeight[]){
segment_tree ST(n);
for (int i=0; i<k; ++i){
if (op[i] == 1){
ST.add(left[i], right[i], height[i]);
} else {
ST.remove(left[i], right[i], height[i]);
}
}
vector<int> res = ST.getState();
for (int i=0; i<n; ++i){
finalHeight[i] = res[i];
}
return;
}