Submission #610855

#	Time	Username	Problem	Language	Result	Execution time	Memory
610855		APROHACK	Wall (IOI14_wall)	C++14	0 / 100	1332 ms	8620 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first 
#define ss second
#define pb push_back
using namespace std;
ll N, K;
vector<ll>ans;
struct segTree
{
  ll dd, ht, mid, val, cual ;
  bool enEspera;
  segTree *L, *R;
  segTree(int l, int r){
    dd = l;
    enEspera = false;
    ht = r;
    val = 0;
    mid = (dd+ht)/2;
    if(dd!=ht){
      L = new segTree(dd, mid);
      R = new segTree(mid+1, ht);
    }
  }
  void propagate(){
    L->up(dd, mid, val);
    R->up(mid+1, ht, val);
    val = 0;
  }
  void lazy(int cur){
    if(dd==ht){
      return;
    }
    if(enEspera){
      L->down(dd, mid, cual);
      R->down(mid+1, ht, cual);
      cual = cur;
      if(cual==-1)enEspera=false;
    }else{
      if(cur==-1)return ;
      enEspera=true;
      cual = cur;
    }
  }
  void up(int l, int r, ll q){
    lazy(-1);
    if(l==dd && r == ht){
      val = max(q, val);
    }else{
      propagate();
      if(r<=mid){
        L->up(l, r, q);
      }else if(mid<l){
        R->up(l, r, q);
      }else{
        L->up(l, mid, q);
        R->up(mid+1, r, q);
      }
    }
    //if(true)//cout<<dd<< " " << ht<< " - >" << val << endl;
  }
  
  void down(int l, int r, ll q){
      if(l==dd && r == ht){
        if(val==0){
          lazy(q);
        }else{
          val = min(q, val);
        }
      }else{
        propagate();
        if(r<=mid){
          L->down(l, r, q);
        }else if(mid<l){
          R->down(l, r, q);
        }else{
          L->down(l, mid, q);
          R->down(mid+1, r, q);
        }
      }
      //cout<<l<< " " << r<< " - >" << val<< endl;
    }

  void answer(){
    lazy(-1);
    if(dd==ht){
      ans.pb(val);
    }else{
      propagate();
      L->answer();
      R->answer();
    }
  }
};



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n, K=k;
  segTree *tri = new segTree(0, n-1);
  for(int i = 0 ; i < k ; i ++){
    if(op[i]==1){
      tri->up(left[i], right[i], height[i]);
    }else tri->down(left[i], right[i], height[i]);
  }
  tri->answer();
  for(int i = 0 ; i < n ; i ++)finalHeight[i]=ans[i];

  return;
}

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