Submission #577530

#	Time	Username	Problem	Language	Result	Execution time	Memory
577530		Belgutei	Wall (IOI14_wall)	C++17	0 / 100	165 ms	13856 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;
int level,zereg[30];
vector<int> add[30], rem[30];
int l,r;

void build() {
  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) {
    rem[k + 1][x * 2] = min(rem[k + 1][x * 2], rem[k][x]);
    if(add[k + 1][x * 2] > rem[k][x]) add[k + 1][x * 2] = rem[k][x];
    //
    rem[k + 1][x * 2 + 1] = min(rem[k + 1][x * 2 + 1], rem[k][x]);
    if(add[k + 1][x * 2 + 1] > rem[k][x]) add[k + 1][x * 2 + 1] = rem[k][x];
    rem[k][x] = -1;
  }
  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;
}

int go(int pos) {
  int ret = 0;
  for(int i = level; i >= 0; i --) {
    if(rem[i][pos] != -1) if(ret > rem[i][pos]) ret = rem[i][pos];
    ret = max(ret, add[i][pos]);
    pos /= 2;
  }
  return ret;
} 

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

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 ++) {
    l = left[i];
    r = right[i];
    dfs(0,0,op[i],height[i]);
  }
  for(int i = 0; i < N; i ++) {
    finalHeight[i] = go(i);
  }
  return; 
}

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