Submission #7289

#	Time	Username	Problem	Language	Result	Execution time	Memory
7289		myungwoo	Wall (IOI14_wall)	C++98	100 / 100	1040 ms	87600 KiB

wall

#include <stdlib.h>
#include <algorithm>
using namespace std;
 
static int N,K,*H;
 
struct NODE{
    NODE(int h=0): mini(h),maxi(h),left(NULL),right(NULL) {}
    int mini,maxi;
    NODE *left,*right;
};
 
void dfs(NODE *now,int s,int e,int l,int r,int mini,int maxi,int op,int h)
{
    if (mini <= now->mini && now->maxi <= maxi);
    else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
    else if (maxi < now->mini) now->mini = now->maxi = maxi;
    else if (now->maxi < mini) now->mini = now->maxi = mini;
    else if (mini > now->mini) now->mini = mini;
    else if (maxi < now->maxi) now->maxi = maxi;
    mini = now->mini; maxi = now->maxi;
    if (e < l || s > r) return;
    if (l <= s && e <= r){
        if (op == 1){   // add
            if (now->mini < h) now->mini = h;
            if (now->maxi < h) now->maxi = h;
        }else{          // remove
            if (now->maxi > h) now->maxi = h;
            if (now->mini > h) now->mini = h;
        }
        return;
    }
    int m = (s+e)>>1;
    if (now->left == NULL){
        now->left = new NODE(now->mini);
        now->right = new NODE(now->mini);
    }
    dfs(now->left,s,m,l,r,mini,maxi,op,h);
    dfs(now->right,m+1,e,l,r,mini,maxi,op,h);
    now->mini = min(now->left->mini,now->right->mini);
    now->maxi = max(now->left->maxi,now->right->maxi);
}
 
void cdfs(NODE *now,int s,int e,int mini,int maxi)
{
    if (mini <= now->mini && now->maxi <= maxi);
    else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
    else if (maxi < now->mini) now->mini = now->maxi = maxi;
    else if (now->maxi < mini) now->mini = now->maxi = mini;
    else if (mini > now->mini) now->mini = mini;
    else if (maxi < now->maxi) now->maxi = maxi;
    mini = now->mini; maxi = now->maxi;
    if (mini == maxi){
        for (int i=s;i<=e;i++) H[i] = mini;
        return;
    }
    int m = (s+e)>>1;
    cdfs(now->left,s,m,mini,maxi);
    cdfs(now->right,m+1,e,mini,maxi);
}
 
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    int i;
    NODE *root = new NODE();
    N = n, K = k;
    for (i=0;i<K;i++){
        dfs(root,0,N-1,left[i],right[i],0,1e9,op[i],height[i]);
    }
    H = finalHeight;
    cdfs(root,0,N-1,0,1e9);
}

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