Submission #555044

#	Time	Username	Problem	Language	Result	Execution time	Memory
555044		Belgutei	Wall (IOI14_wall)	C++17	0 / 100	172 ms	8104 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

int n;

vector<int> add[30];
vector<int> rem[30];

int l,r;
int h, type;
int level,zereg[30];

void build_tree(){
  zereg[0] = 1;
  for(int i = 0; i <= 30; i++){
    if(zereg[i] >= n){
      level = i;
      break;
    }
    zereg[i + 1] = zereg[i] * 2;
  }
  for(int i = 0; i <= level; i++){
    for(int j = 0; j < zereg[i]; j++){
      add[i].pb(-1);
      rem[i].pb(-1);
    }
  }
}

void propogate(int k, int x){
  if(rem[k][x] != -1){
    add[k + 1][x * 2] = min(add[k + 1][x * 2], rem[k][x]);
    add[k + 1][x * 2 + 1] = min(add[k + 1][x * 2 +1], rem[k][x]);
    //
    if(rem[k + 1][x * 2] != -1) rem[k + 1][x * 2] = min(rem[k + 1][x * 2], rem[k][x]);
    else rem[k + 1][x * 2] = rem[k][x];
    //
    if(rem[k + 1][x * 2 + 1] != -1) rem[k + 1][x * 2 + 1] = min(rem[k + 1][x * 2 + 1], rem[k][x]);
    else rem[k + 1][x * 2 + 1] = rem[k][x];
  }
  add[k + 1][x * 2]= max(add[k + 1][x * 2], add[k][x]);
  add[k + 1][x * 2 + 1]= max(add[k + 1][x * 2 + 1], add[k][x]);
  add[k][x] = -1;
  rem[k][x] = -1;
}

void dfs(int k, int x){
  int y = zereg[level - k] * x;
  int z = zereg[level - k] * (x + 1) -1;;
  if(l <= y && z <= r){
    if(type == 1){
      if(add[k][x] < h) {
        add[k][x] = h;
      }
      if(rem[k][x] <= h) rem[k][x] = -1;
    }
    else{
      if(add[k][x] > h){
        add[k][x] = h;
      }
      if(rem[k][x] < h) rem[k][x] = h;
    }
    return;
  }
  if(z < l || y > r || k == level) return;
  propogate(k,x);
  dfs(k + 1, x * 2);
  dfs(k + 1, x * 2 + 1);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = N;
  build_tree();
  for(int i = 0; i < k; i++){
    l = left[i];
    r = right[i];
    h = height[i];
    type = op[i];
    dfs(0,0);
  }
  for(int i = 0; i < n; i++){
    int pos = i;
    for(int j = level; j >= 0; j--){
      if(rem[j][pos] != -1) finalHeight[i] = min(finalHeight[i], rem[j][pos]);
      finalHeight[i] = max(finalHeight[i], add[j][pos]);
      pos /= 2;
    }
  }
  return;
}

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