| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 109954 | DodgeBallMan | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 10;
const int inf = 2e9;
int lo[N<<1], hi[N<<1];
void push( int now, int l, int r ) {
if( l == r ) ret[l] = min( hi[now], max( lo[now], ret[l] ) );
else {
hi[now<<1] = max( lo[now], min( hi[now], hi[now<<1] ) ), lo[now<<1] = min( hi[now], max( lo[now], lo[now<<1] ) );
hi[now<<1|1] = max( lo[now], min( hi[now], hi[now<<1|1] ) ), lo[now<<1|1] = min( high[now], max( lo[now], lo[now<<1|1] ) );
}
lo[now] = 0, hi[now] = inf;
return ;
}
void update( int ll, int rr, int f, int t, int l = 1, int r = n, int now = 1 ) {
push( now, f, t );
if( l > rr || r < ll && l > r ) return ;
if( l >= ll && r <= rr ) {
hi[now] = max( f, min( hi[now], t ) ), lo[now] = min( t, max( lo[now], f ) );
return ;
}
int mid = ( l + r ) >> 1;
update( ll, rr, f, t, l, mid, now << 1 ), update( ll, rr, f, t, mid + 1, r, now << 1 | 1 );
return ;
}
void computeans( int l = 1, int r = n, int now = 1 ) {
push( now, l, r );
if( l == r ) return ;
int mid = ( l + r ) >> 1;
computeans( l, mid, now << 1 ), computeans( mid + 1, r, now << 1 | 1 );
return ;
}
void buildWall( int N, int k, int op[], int left[], int right[], int height[], int finalheight[] )
{
fill( hi, hi + 2*N, inf );
for( int i = 0 ; i < k ; i++ ) {
if( op[i] == 1 ) update( left[i] + 1, right[i] + 1, height[i], inf );
else update( left[i] + 1, right[i] + 1, 0, height[i] );
}
computeans();
for( int i = 1 ; i <= n ; i++ ) finalheight[i-1] = ret[i];
return ;
}