제출 #535288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535288		smth	벽 (IOI14_wall)	C++14	8 / 100	3092 ms	45304 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int mini[8000002],maxi[8000000], lazymin[8000000],lazymax[8000000],fin[2000002];
bool ispmin[8000003], ispmax[8000003];
void add(int le,int ri,int l,int r,int h, int ind)
{
    if(l<=le && ri<=r)
    {
        lazymax[ind]=max(lazymax[ind],h);ispmax[ind]=1;
    }
    if(ispmin[ind])
    {
            mini[ind]=min(mini[ind],lazymin[ind]);
            maxi[ind]=min(maxi[ind],lazymin[ind]);

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=1;
        }
        lazymin[ind]=100000000;ispmin[ind]=0;

    }
    if(ispmax[ind])
    {
        maxi[ind]=max(maxi[ind],lazymax[ind]);
        mini[ind]=max(mini[ind],lazymax[ind]);

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            ispmax[2*ind]=ispmax[2*ind+1]=1;
        }
        lazymax[ind]=0;ispmax[ind]=0;
    }
    if(l<=le && ri<=r&& !ispmin[2*ind] && !ispmin[2*ind+1] && !ispmax[2*ind] && !ispmax[2*ind+1])return;
    if(l>ri || r<le)return;

    int mid=(le+ri)/2;

    add(le,mid,l,r,h,2*ind);
    add(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

}

void rem(int le,int ri,int l,int r,int h, int ind)
{
    if(l<=le && ri<=r)
    {
        lazymin[ind]=min(lazymin[ind],h);
        ispmin[ind]=1;
    }
    if(ispmax[ind])
    {
               maxi[ind]=max(maxi[ind],lazymax[ind]);
               mini[ind]=max(mini[ind],lazymax[ind]);

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            ispmax[2*ind]=ispmax[2*ind+1]=1;
        }
        lazymax[ind]=0;ispmax[ind]=0;
    }

    if(ispmin[ind])
    {
        mini[ind]=min(mini[ind],lazymin[ind]);
        maxi[ind]=min(maxi[ind],lazymin[ind]);

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=1;
        }
        lazymin[ind]=100000000;ispmin[ind]=0;

    }
    if(l<=le && ri<=r && !ispmin[2*ind] && !ispmin[2*ind+1] && !ispmax[2*ind] && !ispmax[2*ind+1])return;
    if(l>ri || r<le)return;

    int mid=(le+ri)/2;

    rem(le,mid,l,r,h,2*ind);
    rem(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

}
void query(int le,int ri,int ind)
{
    if(ispmin[ind])
    {
            mini[ind]=min(mini[ind],lazymin[ind]);
            maxi[ind]=min(maxi[ind],lazymin[ind]);

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=1;
        }
        lazymin[ind]=100000000;ispmin[ind]=0;

    }
    if(ispmax[ind])
    {
        maxi[ind]=max(maxi[ind],lazymax[ind]);
        mini[ind]=max(mini[ind],lazymax[ind]);

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            ispmax[2*ind]=ispmax[2*ind+1]=1;
        }
        lazymax[ind]=0;ispmax[ind]=0;
    }

    if(mini[ind]==maxi[ind])
    {
        for(int i=le;i<=ri;i++)fin[i]=mini[ind];
        return;
    }
    if(le==ri){

      return;
    }

    int mid=(le+ri)/2;
    query(le,mid,2*ind);
    query(mid+1,ri,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;
    for(i=0;i<8000000;i++)lazymin[i]=100000000;
    for(i=0;i<k;i++)
    {
        left[i]++;
        right[i]++;
        if(op[i]==1)add(1,n,left[i],right[i],height[i],1);
        else rem(1,n,left[i],right[i],height[i],1);
    }


    query(1,n,1);

    for(i=0;i<n;i++)finalHeight[i]=fin[i+1];

  return;
}

/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/

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