Submission #610976

#	Time	Username	Problem	Language	Result	Execution time	Memory
610976		APROHACK	Wall (IOI14_wall)	C++14	100 / 100	1283 ms	240340 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;
int N, K, blocksz;
vector<int>ans, ans2;
vector<int>values;
struct segTree
{
  int dd, ht, minimum, maximum, mid;
  segTree *L, *R;
  segTree(int l, int r){
    dd = l, ht = r;
    mid = (l+r)/2;
    minimum = 0, maximum = 1000000000;
    if(l!=r){
      L=new segTree(l, mid);
      R=new segTree(mid+1, r);
    }
  }
  void lazy(){
    L->operate(dd, mid, 1, minimum);
    L->operate(dd, mid, 2, maximum);
    R->operate(mid+1, ht, 1, minimum);
    R->operate(mid+1, ht, 2, maximum);
    minimum = 0;
    maximum = 1000000000;
  }
  void operate(int l, int r, int op, int val){
    if(l == dd && r == ht){
      if(op==1){
        if(minimum < val){
          minimum = val;
          if(maximum < minimum)maximum = minimum;
        }
      }else{
        if(maximum > val){
          maximum = val;
          if(minimum > maximum)minimum = maximum;
        }
      }
    }else{
      lazy();
      if(r<= mid){
        L->operate(l, r, op, val);
      }else if(l > mid){
        R->operate(l, r, op, val);
      }else{
        L->operate(l, mid, op, val);
        R->operate(mid+1, r, op, val);
      }
    }
  }
  void answ(){
    if(dd!=ht){
      lazy();
      L->answ();
      R->answ();
    }else{
      ans.pb(minimum);
    }
  }

};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n, K=k;
  for(int i = 0 ; i < n ; i ++){
    values.pb(0);
  }
  segTree *st = new segTree(0, n-1);
  for(int  i = 0 ; i < k ; ++i){
    st->operate(left[i], right[i], op[i], height[i]);
  }
  st->answ();
  for(int i = 0 ; i < n ; i ++)finalHeight[i] = ans[i];


  return;
}

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