제출 #270729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270729		daniel920712	벽 (IOI14_wall)	C++14	24 / 100	3080 ms	25336 KiB

wall

#include "wall.h"
#include <algorithm>
#include <iostream>
#include <stdio.h>
using namespace std;
int all[1000005]={0};
struct A
{
    int l,r;
    int nxl,nxr;
    int big;
    int small;
    int which;
}Node[4000005];
int now=1;
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].big=-1;
    Node[here].small=-1;
    if(l==r)
    {
        Node[here].which=all[l];
        return ;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
int Find(int where,int here)
{
    if(where==Node[here].l&&where==Node[here].r)
    {
        if(Node[here].big!=-1) return max(Node[here].which,Node[here].big);
        if(Node[here].small!=-1) return min(Node[here].which,Node[here].small);
        return Node[here].which;
    }
    if(where<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].big!=-1) return max(Find(where,Node[here].nxl),Node[here].big);
        if(Node[here].small!=-1) return min(Find(where,Node[here].nxl),Node[here].small);
        return Find(where,Node[here].nxl);
    }
    else
    {
        if(Node[here].big!=-1) return max(Find(where,Node[here].nxr),Node[here].big);
        if(Node[here].small!=-1) return min(Find(where,Node[here].nxr),Node[here].small);
        return Find(where,Node[here].nxr);
    }
}
void cha(int l,int r,int con,int what,int here)
{
    //printf("%d %d %d\n",l,r,here);
    if(Node[here].l==l&&Node[here].r==r)
    {
        if(what==1)
        {
            if(Node[here].big==-1) Node[here].big=con;
            else Node[here].big=max(Node[here].big,con);
        }
        else
        {
            if(Node[here].small==-1) Node[here].small=con;
            else Node[here].small=min(Node[here].small,con);
        }
        return ;
    }
    if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,what,Node[here].nxr);
    else
    {
        cha(l,(Node[here].l+Node[here].r)/2,con,what,Node[here].nxl);
        cha((Node[here].l+Node[here].r)/2+1,r,con,what,Node[here].nxr);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i,j;
    build(0,n-1,0);
    for(i=0;i<k;i++)
    {
        //printf("%d\n",i);
        if(i&&op[i]!=op[i-1])
        {
            for(j=0;j<n;j++) all[j]=Find(j,0);
            now=1;
            build(0,n-1,0);
        }
        cha(left[i],right[i],height[i],op[i],0);
    }
    for(i=0;i<n;i++) finalHeight[i]=Find(i,0);
    return;
}

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