Submission #754669

#	Time	Username	Problem	Language	Result	Execution time	Memory
754669		A_D	Wall (IOI14_wall)	C++17	0 / 100	155 ms	13920 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];
int lazymx[4*N];
int lazymn[4*N]; // miniumum 


void fix(int p,int s,int e)
{
  if(lazymn[p]!=-1){
    if(mn[p]==mx[p]){
      mn[p]=mx[p]=max(mn[p],lazymn[p]);
    }
    else if(mx2[p]==mn[p]){
      mx2[p]=mn[p]=max(mn[p],lazymn[p]);
    }
    mn[p]=max(mn[p],lazymn[p]);
    if(s!=e){
      lazymn[p*2] = lazymn[p*2]!=-1 ? max(lazymn[p*2],lazymn[p]):lazymn[p];
      lazymn[p*2+1] = lazymn[p*2+1]!=-1 ? max(lazymn[p*2+1],lazymn[p]):lazymn[p];
      if(lazymx[p*2]!=-1 && lazymn[p*2]!=-1){
        lazymx[p*2]=max(lazymx[p*2],lazymn[p*2]);
      }
      if(lazymx[p*2+1]!=-1 && lazymn[p*2+1]!=-1){
        lazymx[p*2+1]=max(lazymx[p*2+1],lazymn[p*2+1]);
      }
    }
    lazymn[p]=-1;
  }
  if(lazymx[p]!=-1){
    if(mn[p]==mx[p]){
      mn[p]=mx[p]=min(lazymx[p],mx[p]);
    }
    else if(mn2[p]==mx[p]){
      mn2[p]=mx[p]=min(lazymx[p],mx[p]);
    }
    mx[p]=min(lazymx[p],mx[p]);
    if(s!=e){
      lazymx[p*2] = lazymx[p*2]!=-1 ? min(lazymx[p*2],lazymx[p]):lazymx[p];
      lazymx[p*2+1] = lazymx[p*2+1]!=-1 ? max(lazymx[p*2+1],lazymx[p]):lazymx[p];
      if(lazymn[p*2]!=-1 && lazymx[p*2]!=-1){
        lazymn[p*2]=min(lazymn[p*2],lazymx[p*2]);
      }
      if(lazymn[p*2+1]!=-1 && lazymx[p*2+1]!=-1){
        lazymn[p*2+1]=min(lazymn[p*2+1],lazymx[p*2+1]);
      }
    }
    lazymx[p]=-1;
  }
}
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 ){
        lazymn[p]=h;
        fix(p,s,e);
        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 ){
        lazymx[p]=h;
        fix(p,s,e);
        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;
      lazymn[i]=-1;
      lazymx[i]=-1;
    }
    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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39