제출 #751527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751527		amin	벽 (IOI14_wall)	C++14	100 / 100	1036 ms	84552 KiB

wall

#include "wall.h"
 #include <bits/stdc++.h>
using namespace std;
 #define ll long long

int ma[8000000];
int mi[8000000];
int a[4000003];
int z;
int b[2000003];
int ans=0;
int n;


void push(int v)
{
//cout<<v<<endl;
   if(ma[v]<ma[v*2]&&ma[v]<mi[v*2])
   {
    //   cout<<v<<endl;

       ma[v*2]=mi[v*2]=ma[v];

   }else
   if(mi[v]>mi[v*2]&&mi[v]>ma[v*2])
   {
    mi[v*2]=ma[v*2]=mi[v];
   // cout<<v<<endl;
   }
 else
 {
   mi[v*2]=max(mi[v*2],mi[v]);
   ma[v*2]=min(ma[v*2],ma[v]);
 }
  if(ma[v]<ma[v*2+1]&&ma[v]<mi[v*2+1])
   {
      // cout<<v<<endl;
       ma[v*2+1]=mi[v*2+1]=ma[v];
   }else
   if(mi[v]>mi[v*2+1]&&mi[v]>ma[v*2+1])
   {
      // cout<<v<<endl;
    mi[v*2+1]=ma[v*2+1]=mi[v];
   }
 else
 {
   mi[v*2+1]=max(mi[v*2+1],mi[v]);
   ma[v*2+1]=min(ma[v*2+1],ma[v]);
 }
mi[v]=0;
ma[v]=1e9;
}
void update(int v,int tl,int tr,int l,int r,int t,int val)
{
  //  cout<<tl<<' '<<tr<<endl;
    if(l>r)
        return ;

    if(tl==l&&tr==r)
    {
     //   cout<<tl<<' '<<tr<<endl;
     if(t==1)
     {
         mi[v]=max(mi[v],val);
         ma[v]=max(mi[v],ma[v]);
     }else
     {
         ma[v]=min(ma[v],val);
         mi[v]=min(mi[v],ma[v]);
     }
    /* if(tl==3&&tr==5)
     {
       //  cout<<mi[v]<<' '<<ma[v]<<endl;
     }*/
        return ;

    }
   // cout<<tl<<' '<<tr<<endl;
    push(v);
    int tm=(tl+tr)>>1;
   update(v*2,tl,tm,l,min(r,tm),t,val);
   update(v*2+1,tm+1,tr,max(tm+1,l),r,t,val);
  //  merg(v,v*2,v*2+1);

}
int get(int v,int tl,int tr,int pos)
{
    if(tl>pos||pos>tr)
        return 1000000001;
    if(tl==tr)
    {
      //  cout<<ma[v]<<endl;
        return mi[v];
       // cout<<ma[v]<<endl;
    }
    push(v);
    int tm=(tl+tr)/2;
    return min(get(v*2,tl,tm,pos),get(v*2+1,tm+1,tr,pos));

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

for(int i=0;i<4*n;i++)
{
    ma[i]=1000000000;
}
for(int i=0;i<k;i++)
{
update(1,0,n-1,left[i],right[i],op[i],height[i]);
}

for(int i=0;i<n;i++)
{
    finalHeight[i]=get(1,0,n-1,i);
}
return ;











}

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