Submission #547832

#	Time	Username	Problem	Language	Result	Execution time	Memory
547832		mdn2002	Wall (IOI14_wall)	C++14	0 / 100	452 ms	22524 KiB

wall

#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;
}
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39