| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 307286 | tengiz05 | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
struct Node {
int min;
int max;
};
vector<Node> t;
int no_max = INT_MAX;
int no_min = 0;
int sz;
void init(int n){
sz = 1;
while(sz < n)sz <<= 1;
t.assign(sz*2, {0, 0});
}
void modify(int Max, int Min, int node){
t[node].max = min(Max, max(Min, t[node].max));
t[node].min = min(Max, max(Min, t[node].min));
}
void push(int node, int len){
if(len == 1){
t[node] = {no_min, no_max};
return;
}
modify(t[node].max, t[node].min, node*2);
modify(t[node].max, t[node].min, node*2+1);
t[node] = {no_min, no_max};
}
void add(int l, int r, int L, int R, int node, int Max, int Min){
if(L >= r || R <= l)return;
push(node, R-L);
if(L >= l && R <= r){
modify(Max, Min, node);
return;
}
int mid = (L+R)/2;
add(l, r, L, mid, node*2, Max, Min);
add(l, r, mid, R, node*2+1,Max,Min);
}
void add(int l, int r, int Max, int Min){
add(l, r, 0, sz, 1, Max, Min);
}
int get(int i, int L, int R, int node){
if(R-L == 1){
return t[node].min;
}
push(node, R-L);
int mid = (L+R)/2;
if(i < mid)return get(i, L, mid, node*2);
else return get(i, mid, R, node*2+1);
}int get(int i){
int ans = max(get(i, 0, sz, 1), 0);
return ans;
}
/*
void print(){
cout << '\n';
for(int i=1;i<sz*2;i++){
cout << t[i].min << ' ' << t[i].max << '\n';
}cout << "\n\n";
}*/
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree seg;
seg.init(n);
for(int i=0;i<k;i++){
// seg.print();
if(op[i] == 2){
// add
seg.add(left[i], right[i]+1, height[i], seg.no_min);
}else {
// remove
seg.add(left[i], right[i]+1, seg.no_max, height[i]);
}
}//seg.print();
for(int i=0;i<n;i++){
finalHeight[i] = seg.get(i);
// seg.print();
}
return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/