Submission #1272073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272073		thunopro	Wall (IOI14_wall)	C++20	61 / 100	421 ms	14652 KiB

wall

#include "wall.h"
#include<bits/stdc++.h> 
using namespace std; 
const int INF = 1e9 ; 
#define maxn 200009 
#define left id<<1
#define right id<<1|1 
struct shape{
    int Min , Max ; 
} T [maxn*4] ; 

void fmax ( int id , int w ) 
{
    if ( T[id].Min < w ) T [id].Min = w ; 
    if ( T[id].Max < w ) T [id].Max = w ; 
}
void fmin ( int id , int w ) 
{
    if ( T[id].Min > w ) T [id].Min = w ; 
    if ( T[id].Max > w ) T [id].Max = w ; 
}
void down ( int id ) 
{
    fmax (left,T[id].Max) , fmax (right,T[id].Max) ; 
    fmin (left,T[id].Min) , fmin (right,T[id].Min) ; 
    T [id].Max = 0 , T [id].Min = INF ; 
}
void update ( int id , int l , int r , int u , int v , int w , int type ) 
{
    if ( l > v || r < u ) return ; 
    if ( u <= l && r <= v ) 
    {
        if ( type == 1 ) fmax (id,w) ; 
        else fmin (id,w) ; 
        return ; 
    }
    down (id) ; 
    int mid = (l+r)/2 ; 
    update (left,l,mid,u,v,w,type) ; 
    update (right,mid+1,r,u,v,w,type) ;  
}

int get ( int id , int l , int r , int pos ) 
{
    if ( l > pos || r < pos ) return 0 ; 
    if ( l == r ) return T [id].Max ; 
    down (id) ; 
    int mid = (l+r)/2 ; 
    return max(get(left,l,mid,pos),get(right,mid+1,r,pos)) ; 
}
void buildWall(int n, int k, int op[], int l[], int r[], int height[], int finalHeight[]){
    for ( int i = 0 ; i < n*4 ; i ++ ) T [i].Min = INF ; 
    for ( int i = 0 ; i < k ; i ++ ) 
    {
        update (1,0,n-1,l[i],r[i],height[i],op[i]) ; 
    }
    for ( int i = 0 ; i < n ; i ++ ) finalHeight [i] = get (1,0,n-1,i) ; 
    return ; 
}

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