Submission #529065

#	Time	Username	Problem	Language	Result	Execution time	Memory
529065		Gurban	Wall (IOI14_wall)	C++17	24 / 100	447 ms	21768 KiB

wall

#include "bits/stdc++.h"
#include "wall.h"
using namespace std;

using ll = long long;

const int maxn=2e6+5;
const int N = 5e5+5;

int T[4 * maxn][2];

void build(int l,int r,int nd){
  T[nd][1] = 1e5;
  if(l == r) return;
  int md = (l + r) >> 1;
  build(l,md,nd<<1);
  build(md+1,r,nd<<1 | 1);
}

void prop(int nd){

  if(T[nd][0] == -1) return;

  int cep = (nd << 1);
  int sag = (nd << 1 | 1);

  if(T[cep][0] == -1){
    T[cep][0] = T[nd][0];
    T[cep][1] = T[nd][1];
  }
  else if(T[cep][0] > T[nd][1]){
    T[cep][0] = T[nd][1];
    T[cep][1] = T[nd][1];
  }
  else if(T[cep][1] < T[nd][0]){
    T[cep][0] = T[nd][0];
    T[cep][1] = T[nd][0];
  }
  else {
    T[cep][0] = max(T[cep][0],T[nd][0]);
    T[cep][1] = min(T[cep][1],T[nd][1]);
  }
  
  if(T[sag][0] == -1){
    T[sag][0] = T[nd][0];
    T[sag][1] = T[nd][1];
  }
  else if(T[sag][0] > T[nd][1]){
    T[sag][0] = T[nd][1];
    T[sag][1] = T[nd][1];
  }
  else if(T[sag][1] < T[nd][0]){
    T[sag][0] = T[nd][0];
    T[sag][1] = T[nd][0];
  }
  else {
    T[sag][0] = max(T[sag][0],T[nd][0]);
    T[sag][1] = min(T[sag][1],T[nd][1]);
  }

  T[nd][0] = -1;
  T[nd][1] = -1;
}

void upd(int a,int b,int lft,int rgt,int l,int r,int nd){
  if(r < a or l > b) return;
  if(l >= a and r <= b){
    
    if(T[nd][0] == -1){
      T[nd][0] = lft;
      T[nd][1] = rgt;
      return;
    }

    if(rgt < T[nd][0]){
      T[nd][0] = rgt;
      T[nd][1] = rgt;
    }
    else if(lft > T[nd][1]){
      T[nd][0] = lft;
      T[nd][1] = rgt;
    }
    else {
      T[nd][0] = max(T[nd][0],lft);
      T[nd][1] = min(T[nd][1],rgt);
    }
    return;
  }
  prop(nd);
  int md = (l + r) >> 1;
  upd(a,b,lft,rgt,l,md,nd<<1);
  upd(a,b,lft,rgt,md+1,r,nd<<1 | 1);
}

int jog[maxn];

void f(int l,int r,int nd){
  if(l == r){
    jog[l] = T[nd][0];
    return;
  }
  prop(nd);
  int md = (l + r) >> 1;
  f(l,md,nd<<1);
  f(md+1,r,nd<<1 | 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  build(0,n-1,1);
  for(int i = 0;i < k;i++){

    // cout<<left[i]<<' '<<right[i]<<' '<<height[i]<<'\n';

    if(op[i] == 2) upd(left[i],right[i],0,height[i],0,n-1,1);
    else upd(left[i],right[i],height[i],1e5,0,n-1,1);
  }
  f(0,n-1,1);
  for(int i = 0;i < n;i++){
    finalHeight[i] = jog[i];
    // cout<<jog[i]<<' ';
  }
  return;
}

// int n,k;
// int op[N],l[N],r[N],h[N],ans[maxn];

// int main(){

//   cin >> n >> k;
//   for(int i = 0;i < k;i++) cin >> op[i] >> l[i] >> r[i] >> h[i];
//   buildWall(n,k,op,l,r,h,ans);
//   for(int i = 0;i < n;i++) cout<<ans[i]<<' ';
// }

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