Submission #972835

#	Time	Username	Problem	Language	Result	Execution time	Memory
972835		sleepntsheep	Wall (IOI14_wall)	C11	0 / 100	765 ms	26588 KiB

wall

#include "wall.h"

#define MAX_N 2000002

int chmax[MAX_N<<2], chmin[MAX_N<<2], min[MAX_N<<2], max[MAX_N<<2];

void pull(int v)
{
    min[v]=min[v<<1|(min[v<<1]>min[v<<1|1])];
    max[v]=max[v<<1|(max[v<<1]<max[v<<1|1])];
}

void do_chmax(int v,int l,int r,int k)
{
    if(chmax[v]!=-1&&k<chmax[v])k=chmax[v];
    if(chmin[v]!=-1&&chmin[v]<=k){chmin[v]=-1,chmax[v]=k;}
    chmax[v]=k;
    if(k>=max[v])min[v]=max[v]=k;
    else if(k>=min[v])min[v]=k;
}

void do_chmin(int v,int l,int r,int k)
{
    if(chmin[v]!=-1&&k>chmin[v])k=chmin[v];
    if(chmax[v]!=-1&&chmax[v]>=k){chmax[v]=-1,chmin[v]=k;}
    chmin[v]=k;
    if(chmin[v]<min[v])min[v]=max[v]=chmin[v];
    else if(chmin[v]<max[v])max[v]=chmin[v];
}

void push(int v,int l,int r)
{
    if(chmin[v]!=-1)
    {
        if(l!=r) do_chmin(v<<1,l,l+(r-l)/2,chmin[v]),do_chmin(v<<1|1,l+(r-l)/2+1,r,chmin[v]);
        chmin[v]=-1;
    }
    if(chmax[v]!=-1)
    {
        if(l!=r) do_chmax(v<<1|1,l+(r-l)/2+1,r,chmax[v]),do_chmax(v<<1,l,l+(r-l)/2,chmax[v]);
        chmax[v]=-1;
    }
}

void do_do(int v,int l,int r,int x,int y,int k,void(*op)(int,int,int,int))
{
    push(v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y){op(v,l,r,k);push(v,l,r);return ;}
    do_do(v<<1,l,l+(r-l)/2,x,y,k,op),do_do(v<<1|1,l+(r-l)/2+1,r,x,y,k,op);
    pull(v);
}

void build(int v,int l,int r)
{
    chmin[v]=chmax[v]=-1;
    if(l==r)min[v]=max[v]=0;
    else build(v<<1,l,l+(r-l)/2),build(v<<1|1,l+(r-l)/2+1,r),pull(v);
}

void ans(int v,int l,int r,int *o)
{
    push(v,l,r);
    if(l==r){o[l]=min[v];return;}
    ans(v<<1,l,l+(r-l)/2,o),ans(v<<1|1,l+(r-l)/2+1,r,o);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1,0,n-1);
    for(int i=0;i<k;++i)
        if(op[i]==2)do_do(1,0,n-1,left[i],right[i],height[i],do_chmin);
        else do_do(1,0,n-1,left[i],right[i],height[i],do_chmax);
    ans(1,0,n-1,finalHeight);
}

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