Submission #413389

#	Time	Username	Problem	Language	Result	Execution time	Memory
413389		pliam	Wall (IOI14_wall)	C++14	100 / 100	1293 ms	85264 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000005
#define INF (int)1e9+5

int st[4*MAXN],lazy_lower[4*MAXN],lazy_upper[4*MAXN];//minimum segment tree
int final[MAXN];
int N;

void update(int from,int to,int low,int up,int v=1,int start=0,int end=N-1){
  if(start==from&&end==to){
    st[v]=max(st[v],low);
    st[v]=min(st[v],up);
    if(low>lazy_upper[v]){
      lazy_upper[v]=lazy_lower[v]=low;
    }else if(up<lazy_lower[v]){
      lazy_lower[v]=lazy_upper[v]=up;
    }else{
      lazy_lower[v]=max(lazy_lower[v],low);
      lazy_upper[v]=min(lazy_upper[v],up);
    }
    return;
  }
  int mid=(start+end)/2;
  //propagate
  update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
  update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
  lazy_lower[v]=0;
  lazy_upper[v]=INF;

  if(to<=mid){
    update(from,to,low,up,2*v,start,mid);
  }else if(from>mid){
    update(from,to,low,up,2*v+1,mid+1,end);
  }else{
    update(from,mid,low,up,2*v,start,mid);
    update(mid+1,to,low,up,2*v+1,mid+1,end);
  }
  st[v]=min(st[2*v],st[2*v+1]);
}

void build(int v=1,int start=0,int end=N-1){
  if(start==end){
    lazy_upper[v]=INF;
    return;
  }
  int mid=(start+end)/2;
  build(2*v,start,mid);
  build(2*v+1,mid+1,end);
  lazy_upper[v]=INF;
}

void build_result(int v=1,int start=0,int end=N-1){
  if(start==end){
    final[start]=st[v];
    return;
  }
  int mid=(start+end)/2;
  //propagate
  update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
  update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
  lazy_lower[v]=0;
  lazy_upper[v]=INF;

  build_result(2*v,start,mid);
  build_result(2*v+1,mid+1,end);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n;
  build();
  for(int i=0;i<k;i++){
    if(op[i]==1){
      update(left[i],right[i],height[i],INF);
    }else{
      update(left[i],right[i],0,height[i]);
    }
  }
  build_result();
  for(int i=0;i<n;i++){
    finalHeight[i]=final[i];
  }
  return;
}

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