Submission #587795

#	Time	Username	Problem	Language	Result	Execution time	Memory
587795		yutabi	Wall (IOI14_wall)	C++14	61 / 100	618 ms	26964 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;




int N;

int mini[4000007];
int maxi[4000007];


void add_mini(int node, int val)
{
    if(val==-1)
    {
        return;
    }

    if(mini[node]==-1)
    {
        mini[node]=val;
    }

    mini[node]=max(mini[node],val);

    if(maxi[node]!=-1)
    {
        maxi[node]=max(mini[node],maxi[node]);
    }
}

void add_maxi(int node, int val)
{
    if(val==-1)
    {
        return;
    }
    
    if(maxi[node]==-1)
    {
        maxi[node]=val;
    }

    maxi[node]=min(maxi[node],val);

    if(mini[node]!=-1)
    {
        mini[node]=min(maxi[node],mini[node]);
    }
}


void update_mini(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
    if(hl<=l && r<=hr)
    {
        add_mini(node,h);

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    int m=(l+r)/2;

    if(hl<=m)
    {
        update_mini(hl,hr,h,node*2,l,m);
    }

    if(m+1<=hr)
    {
        update_mini(hl,hr,h,node*2+1,m+1,r);
    }
}


void update_maxi(int hl, int hr, int h, int node=1, int l=0, int r=N-1)
{
    if(hl<=l && r<=hr)
    {
        add_maxi(node,h);

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    int m=(l+r)/2;

    if(hl<=m)
    {
        update_maxi(hl,hr,h,node*2,l,m);
    }

    if(m+1<=hr)
    {
        update_maxi(hl,hr,h,node*2+1,m+1,r);
    }
}

int* res;

void last(int node=1, int l=0, int r=N-1)
{
    if(l==r)
    {
        res[l]=mini[node];

        return;
    }

    add_mini(node*2,mini[node]);
    add_maxi(node*2,maxi[node]);
    
    add_mini(node*2+1,mini[node]);
    add_maxi(node*2+1,maxi[node]);

    mini[node]=-1;
    maxi[node]=-1;

    last(node*2,l,(l+r)/2);
    last(node*2+1,(l+r)/2+1,r);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    N=n;

    res=finalHeight;

    for(int i=0;i<k;i++)
    {
        if(op[i]==1)
        {
            update_mini(left[i],right[i],height[i]);
        }

        else
        {
            update_maxi(left[i],right[i],height[i]);
        }
    }

    last();


    return;
}

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