| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 547835 | mdn2002 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int n , m , treemx [8000006] , treemn [8000006];
pair < int , int > lazy [8000006];
void push ( int nod , int l , int r )
{
if ( lazy [nod] . first == 0 ) return;
if ( lazy [nod] . first == 1 )
{
treemn [nod] = lazy [nod] . second;
treemx [nod] = max ( treemx [nod] , treemn [nod] );
}
if ( lazy [nod] . first == 2 )
{
treemx [nod] = lazy [nod] . second;
treemn [nod] = min ( treemn [nod] , treemx [nod] );
}
if ( l != r )
{
if ( lazy [ nod * 2 ] . first == 0 )
{
if ( lazy [nod] . first == 1 && treemn [ nod * 2 ] <= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
if ( lazy [nod] . first == 2 && treemx [ nod * 2 ] >= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
}
if ( lazy [ nod * 2 ] . first == 1 )
{
if ( lazy [nod] . first == 1 && lazy [ nod * 2 ] . second <= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
if ( lazy [nod] . first == 2 && lazy [ nod * 2 ] . second >= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
}
if ( lazy [ nod * 2 ] . first == 2 )
{
if ( lazy [nod] . first == 1 && lazy [ nod * 2 ] . second <= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
if ( lazy [nod] . first == 2 && lazy [ nod * 2 ] . second >= lazy [nod] . second ) lazy [ nod * 2 ] = lazy [nod];
}
if ( lazy [ nod * 2 + 1 ] . first == 0 )
{
if ( lazy [nod] . first == 1 && treemn [ nod * 2 + 1 ] <= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
if ( lazy [nod] . first == 2 && treemx [ nod * 2 + 1 ] >= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
}
if ( lazy [ nod * 2 + 1 ] . first == 1 )
{
if ( lazy [nod] . first == 1 && lazy [ nod * 2 + 1 ] . second <= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
if ( lazy [nod] . first == 2 && lazy [ nod * 2 + 1 ] . second >= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
}
if ( lazy [ nod * 2 + 1 ] . first == 2 )
{
if ( lazy [nod] . first == 1 && lazy [ nod * 2 + 1 ] . second <= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
if ( lazy [nod] . first == 2 && lazy [ nod * 2 + 1 ] . second >= lazy [nod] . second ) lazy [ nod * 2 + 1 ] = lazy [nod];
}
}
lazy [nod] = { 0 , 0 };
}
void up ( int nod , int l , int r , int x , int y , int a , int b )
{
push ( nod , l , r );
if ( y < l || r < x ) return;
if ( x <= l && r <= y )
{
if ( a == 1 && treemn [nod] <= b ) lazy [nod] = { a , b };
if ( a == 2 && treemx [nod] >= b ) lazy [nod] = { a , b };
push ( nod , l , r );
return;
}
int mid = ( l + r ) / 2;
up ( nod * 2 , l , mid , x , y , a , b );
up ( nod * 2 + 1 , mid + 1 , r , x , y , a , b );
treemx [nod] = max ( treemx [ nod * 2 ] , treemx [ nod * 2 + 1 ] );
treemx [nod] = max ( treemx [nod] , max ( treemn [ nod * 2 ] , treemn [ nod * 2 + 1 ] ) );
treemn [nod] = min ( treemx [ nod * 2 ] , treemx [ nod * 2 + 1 ] );
treemn [nod] = min ( treemn [nod] , min ( treemn [ nod * 2 ] , treemn [ nod * 2 + 1 ] ) );
}
int qr ( int nod , int l , int r , int x , int y )
{
push ( nod , l , r );
if ( y < l || r < x ) return -1;
if ( x <= l && r <= y ) return treemx [nod];
int mid = ( l + r ) / 2;
return max ( qr ( nod * 2 , l , mid , x , y ) , qr ( nod * 2 + 1 , mid + 1 , r , x , y ) );
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
up ( 1 , 0 , n , 0 , n , 0 , 2 );
for (int i = 0; i < k; i++) {
up ( 1 , 0 , n , left [i] , right [i] , op [i] , height [i] );
}
for (int i = 0; i < n; i++) {
finalHeight[i] = qr ( 1 , 0 , n , i , i );
}
}
int main()
{
cin >> n >> m;
up ( 1 , 0 , n , 0 , n , 2 , 0 );
while ( m -- )
{
int t , l , r , x;
cin >> t >> l >> r >> x;
up ( 1 , 0 , n , l , r , t , x );
//cout << ' ' << qr ( 1 , 0 , n , 8 , 8 ) << endl;
}
for ( int i = 0 ; i < n ; i ++ ) cout << qr ( 1 , 0 , n , i , i ) << endl;
}