Submission #754703

#	Time	Username	Problem	Language	Result	Execution time	Memory
754703		A_D	Wall (IOI14_wall)	C++17	100 / 100	1562 ms	162092 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define F first
#define S second
using namespace std;

const int N=2e6+100;

int mx[4*N];
int mx2[4*N];
int mn[4*N];
int mn2[4*N];

void chmn(int p,int s,int e,int h)
{
  if(mn[p]>=h){
    return;
  }
  mn[p]=h;
  if(mx[p]<h){
    mx[p]=h;
    mx2[p]=-1e9;
  }
  else if(mx2[p]<h){
    mx2[p]=h;
  }
}

void chmx(int p,int s,int e,int h)
{
  if(mx[p]<=h){
    return;
  }
  mx[p]=h;
  if(mn[p]>h){
    mn[p]=h;
    mn2[p]=1e9;
  }
  else if(mn2[p]<h){
    mn2[p]=h;
  }
}

void fix(int p,int s,int e)
{
  if(s!=e){
    int mid=(s+e)/2;
    chmn(p*2,s,mid,mn[p]);
    chmn(p*2+1,mid+1,e,mn[p]);

    chmx(p*2,s,mid,mx[p]);
    chmx(p*2+1,mid+1,e,mx[p]);
  }
}
void com(int p,int s,int e)
{
  int a[]={mn[p*2],mn[p*2+1],mn2[p*2],mn2[p*2+1]};
  sort(a,a+4);
  mn[p]=a[0];
  mn2[p]=a[1]!=a[0] ? a[1] : a[2];
  int b[]={mx[p*2],mx[p*2+1],mx2[p*2],mx2[p*2+1]};
  sort(b,b+4);
  mx[p]=b[3];
  mx2[p]=b[2]!=b[3] ? b[2] : b[1];
}


void update(int p,int s,int e,int a,int b,int h,int t)
{
    if(t==1){
      fix(p,s,e);
      if(s>b || e<a || mn[p]>=h){
        return;
      }
      if( a<=s && e<=b && mn2[p]>h ){
        chmn(p,s,e,h);
        return;
      }
      int mid=(s+e)/2;
      update(p*2,s,mid,a,b,h,t);
      update(p*2+1,mid+1,e,a,b,h,t);
      com(p,s,e);
    }
    else{
      fix(p,s,e);
      if(s>b || e<a || mx[p]<=h){
        return;
      }
      if( a<=s && e<=b && mx2[p]<h ){
        chmx(p,s,e,h);
        return;
      }
      int mid=(s+e)/2;
      update(p*2,s,mid,a,b,h,t);
      update(p*2+1,mid+1,e,a,b,h,t);
      com(p,s,e);
    }
}
int get(int p,int s,int e,int i)
{
  fix(p,s,e);
  
  if(s==e){
    return mx[p];
  }
  int mid=(s+e)/2;
  if(i<=mid){
    return get(p*2,s,mid,i);
  }
  else{
    return get(p*2+1,mid+1,e,i);
  }
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=1;i<=4*n;i++){
      mn[i]=mx[i]=0;
      mn2[i]=1e9;
      mx2[i]=-1e9;
    }
    for(int i=0;i<k;i++){
      update(1,0,n-1,left[i],right[i],height[i],op[i]);
    }
    for(int i=0;i<n;i++){
      finalHeight[i]=get(1,0,n-1,i);
    }
    //cout<<"\n";
}

// https://oj.uz/problem/submit/IOI14_wall

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