oj.uz

Submission #109962

# Submission time Handle Problem Language Result Execution time Memory
109962 2019-05-08T13:01:31 Z DodgeBallMan Wall (IOI14_wall) C++14
0 / 100
 689 ms 21924 KB 
#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], ret[N], n, k;

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( hi[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 ) {
    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 ;
    }
    push( now, f, t );
    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[] ) 
{  
    n = N;
    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 ;
}

//#define LOCAL_TEST 0

#ifdef LOCAL_TEST
int main() 
{

    scanf("%d %d",&n,&k);
    for( int i = 0 ; i < k ; i++ ) {
        int op, l, r, h;
        scanf("%d %d %d %d",&op,&l,&r,&h);
        if( op == 1 ) update( l + 1, r + 1, h, inf );
        else update( l + 1, r + 1, 0, h );
        /*computeans();
        for( int i = 1 ; i <= n ; i++ ) printf("%d ",ret[i]);
        cout << endl;*/
    }
    computeans();
    for( int i = 1 ; i <= n ; i++ ) printf("%d ",ret[i]);
    cout << endl;
    return 0;
}
#endif

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Incorrect 8 ms 896 KB Output isn't correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 174 ms 8108 KB Output is correct
3 Correct 214 ms 8184 KB Output is correct
4 Correct 689 ms 20828 KB Output is correct
5 Incorrect 478 ms 21924 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 14 ms 816 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Incorrect 9 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Incorrect 10 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -