| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 333479 | wildturtle | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector < pair < long long, long long > > tree;
void apply(long long node,long long L,long long R) {
tree[node].first=max(min(tree[node].first,R),L);
tree[node].second=max(min(tree[node].second,R),L);
}
void push(long long node,long long le,long long ri) {
if(le<ri) {
apply(2*node,tree[node].first,tree[node].second);
apply(2*node+1,tree[node].first,tree[node].second);
}
tree[node].second=1e9+3;
tree[node].first=0;
}
void go(long long node,long long le,long long ri,long long finalHeight[]) {
if(le==ri) { finalHeight[le]=tree[node].first; return; }
push(node,le,ri);
go(2*node,le,(le+ri)/2,finalHeight);
go(2*node+1,(le+ri)/2,ri,finalHeight);
}
void update(long long node,long long le,long long ri,long long start,long long end,long long cur1,long long cur2) {
if(ri<start || le>end) return;
if(start<=le && ri<=end) { apply(node,cur1,cur2); return; }
push(node,le,ri);
update(2*node,le,(le+ri)/2,start,end,cur1,cur2);
update(2*node+1,(le+ri)/2,ri,start,end,cur1,cur2);
}
void buildWall(long long n,long long k,long long op[],long long left[],long long right[],long long height[],long long finalHeight[]) {
tree.resize(4*n+1);
for(long long i=1;i<=k;i++) {
if(op[i]==1) update(1,1,n,left[i],right[i],height[i],1e9+5);
else update(1,1,n,left[i],right[i],-(1e9+5),height[i]);
}
go(1,1,n,finalHeight);
}