oj.uz

답안 #548114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548114 2022-04-12T13:12:44 Z mdn2002 벽 (IOI14_wall) C++14
100 / 100
 1256 ms 102504 KB 
#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] . second == 1e6 && lazy [nod] . first == -1 ) return;
    treemx [nod] = min ( treemx [nod] , lazy [nod] . second );
    treemn [nod] = max ( treemn [nod] , lazy [nod] . first );
    if ( treemx [nod] < treemn [nod] )
    {
        if ( treemx [nod] == lazy [nod] . second ) treemn [nod] = treemx [nod];
        if ( treemn [nod] == lazy [nod] . first ) treemx [nod] = treemn [nod];
    }
    if ( l != r )
    {
        int mx = max ( lazy [nod] . first , lazy [ nod * 2 ] . first ) , mn = min ( lazy [nod] . second , lazy [ nod * 2 ] . second );
        if ( mx <= mn ) lazy [ nod * 2 ] = { mx , mn };
        else
        {
            if ( mn == lazy [nod] . second ) lazy [ nod * 2 ] = { mn , mn };
            if ( mx == lazy [nod] . first ) lazy [ nod * 2 ] = { mx , mx };
        }
        mx = max ( lazy [nod] . first , lazy [ nod * 2 + 1 ] . first ) , mn = min ( lazy [nod] . second , lazy [ nod * 2 + 1 ] . second );
        if ( mx <= mn ) lazy [ nod * 2 + 1 ] = { mx , mn };
        else
        {
            if ( mn == lazy [nod] . second ) lazy [ nod * 2 + 1 ] = { mn , mn };
            if ( mx == lazy [nod] . first ) lazy [ nod * 2 + 1 ] = { mx , mx };
        }
    }
    lazy [nod] = { -1 , 1e6 };
}
void bld ( int nod , int l , int r )
{
    lazy [nod] = { -1 , 1e6 };
    if ( l == r ) return;
    int mid = ( l + r ) / 2;
    bld ( nod * 2 , l , mid );
    bld ( nod * 2 + 1 , mid + 1 , r );
}
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 )
    {
        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 )
    {
        if ( l == r && treemx [nod] != treemn [nod] )
        {
            cout << 0 / 0;
        }
        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[]){
    bld ( 1 , 0 , n );
    up ( 1 , 0 , n , 0 , n , 0 , 2 );
  for (int i = 0; i < k; i++) {
        if ( op [i] == 1 ) up ( 1 , 0 , n , left [i] , right [i] , height [i] , 1e6 );
        if ( op [i] == 2 ) up ( 1 , 0 , n , left [i] , right [i] , -1 , height [i] );
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = qr ( 1 , 0 , n , i , i );
  }
}
/*
int main()
{
    scanf ( "%d%d" , &n , &m );
    bld ( 1 , 0 , n );
    //up ( 1 , 0 , n , 0 , n , 2 , 0 );
    while ( m -- )
    {
        int t , l , r , x;
        scanf ( "%d%d%d%d" , &t , &l , &r , &x );
        if ( t == 1 ) up ( 1 , 0 , n , l , r , x , 1e6 );
        if ( t == 2 ) up ( 1 , 0 , n , l , r , -1 , x );
    }
    for ( int i = 0 ; i < n ; i ++ ) printf ( "%d\n" , qr ( 1 , 0 , n , i , i ) );
}
*/

Compilation message

wall.cpp: In function 'int qr(int, int, int, int, int)':
wall.cpp:69:23: warning: division by zero [-Wdiv-by-zero]
   69 |             cout << 0 / 0;
      |                     ~~^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1044 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 8 ms 980 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 151 ms 13896 KB Output is correct
3 Correct 214 ms 8436 KB Output is correct
4 Correct 702 ms 22440 KB Output is correct
5 Correct 319 ms 23424 KB Output is correct
6 Correct 300 ms 21928 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 10 ms 1064 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 7 ms 1048 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 147 ms 13888 KB Output is correct
9 Correct 215 ms 8540 KB Output is correct
10 Correct 695 ms 22392 KB Output is correct
11 Correct 304 ms 23572 KB Output is correct
12 Correct 302 ms 21896 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 149 ms 13972 KB Output is correct
15 Correct 51 ms 2520 KB Output is correct
16 Correct 893 ms 22692 KB Output is correct
17 Correct 313 ms 22092 KB Output is correct
18 Correct 309 ms 22176 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 11 ms 1016 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 161 ms 13952 KB Output is correct
9 Correct 218 ms 8396 KB Output is correct
10 Correct 694 ms 22492 KB Output is correct
11 Correct 313 ms 23460 KB Output is correct
12 Correct 292 ms 21924 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 147 ms 13936 KB Output is correct
15 Correct 56 ms 2508 KB Output is correct
16 Correct 897 ms 22828 KB Output is correct
17 Correct 318 ms 22064 KB Output is correct
18 Correct 313 ms 22060 KB Output is correct
19 Correct 1256 ms 102388 KB Output is correct
20 Correct 1203 ms 100112 KB Output is correct
21 Correct 1224 ms 102504 KB Output is correct
22 Correct 1213 ms 99780 KB Output is correct
23 Correct 1206 ms 99956 KB Output is correct
24 Correct 1215 ms 99824 KB Output is correct
25 Correct 1221 ms 99912 KB Output is correct
26 Correct 1251 ms 102480 KB Output is correct
27 Correct 1244 ms 102280 KB Output is correct
28 Correct 1215 ms 99920 KB Output is correct
29 Correct 1201 ms 100064 KB Output is correct
30 Correct 1214 ms 99832 KB Output is correct