Submission #7607

#	Time	Username	Problem	Language	Result	Execution time	Memory
7607		dohyun0324	Wall (IOI14_wall)	C++98	100 / 100	940 ms	49496 KiB

wall

#include "wall.h"
#include<algorithm>
using namespace std;
int c=1;
struct data
{
    int mini,maxi;
}tree[4194400];

void spread(int k)
{
    if(tree[k*2].mini<tree[k].mini)
    {
        tree[k*2].mini=tree[k].mini;
        tree[k*2].maxi=max(tree[k*2].maxi,tree[k*2].mini);
    }
    if(tree[k*2].maxi>tree[k].maxi)
    {
        tree[k*2].maxi=tree[k].maxi;
        tree[k*2].mini=min(tree[k*2].mini,tree[k*2].maxi);
    }
    if(tree[k*2+1].mini<tree[k].mini)
    {
        tree[k*2+1].mini=tree[k].mini;
        tree[k*2+1].maxi=max(tree[k*2+1].maxi,tree[k*2+1].mini);
    }
    if(tree[k*2+1].maxi>tree[k].maxi)
    {
        tree[k*2+1].maxi=tree[k].maxi;
        tree[k*2+1].mini=min(tree[k*2+1].mini,tree[k*2+1].maxi);
    }
}
void Plus(int k,int x,int y,int s,int e,int h)
{
    if(y<s || x>e) return;
    if(x>=s && y<=e)
    {
        tree[k].mini=max(tree[k].mini,h);
        tree[k].maxi=max(tree[k].maxi,tree[k].mini);
        return;
    }
    spread(k);
    Plus(k*2,x,(x+y)/2,s,e,h);
    Plus(k*2+1,(x+y)/2+1,y,s,e,h);
    tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
    tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void Minus(int k,int x,int y,int s,int e,int h)
{
    if(y<s || x>e) return;
    if(x>=s && y<=e)
    {
        tree[k].maxi=min(h,tree[k].maxi);
        tree[k].mini=min(tree[k].mini,tree[k].maxi);
        return;
    }
    spread(k);
    Minus(k*2,x,(x+y)/2,s,e,h);
    Minus(k*2+1,(x+y)/2+1,y,s,e,h);
    tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
    tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;
    for(i=1;;i++)
    {
        if(c>=n) break;
        c*=2;
    }
    for(i=0;i<k;i++)
    {
        if(op[i]==1) Plus(1,1,c,left[i]+1,right[i]+1,height[i]);
        else Minus(1,1,c,left[i]+1,right[i]+1,height[i]);
    }
    for(i=1;i<c;i++)
    {
        if(i==11)
        {
            i=11;
        }
        spread(i);
    }
    for(i=c;i<=c+n-1;i++)
    {
        finalHeight[i-c]=tree[i].mini;
    }
    return;
}

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