제출 #566066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566066		elira	Wall (IOI14_wall)	C++14	0 / 100	259 ms	262144 KiB

wall

#include "wall.h"
//#include <stdio.h>

struct Node
{

  Node(int start, int end, int value)
  {
    this->start = start;
    this->end = end;
    this->value = value;
    this->min_value = value;
    this->max_value = value;
  }
  ~Node()
  {
    if (left != nullptr)
    {
      delete left;
    }
    if (right != nullptr)
    {
      delete right;
    }
  }

  void SetValueForRange(int value)
  {
    this->value = value;
    this->min_value = value;
    this->max_value = value;
    if (left)
      delete left;
    if (right)
      delete right;
  }

  int start, end;

  int value;
  int min_value, max_value;
  Node *left = nullptr;
  Node *right = nullptr;
};

inline int max(int a, int b)
{
  if (a > b)
  {
    return a;
  }
  return b;
}

inline int min(int a, int b)
{
  if (a < b)
  {
    return a;
  }
  return b;
}

void updateAdd(int start, int end, int value, Node *node) {
  if (start == node->start && end == node->end ) {
    if (node->max_value <= value) {
      node->SetValueForRange(value);
      return;
    }
    if (node->min_value >= value) {
      return;
    }
  }
  int middle = (node->start + node->end) / 2;

  if (node->left == nullptr) {
    node->left = new Node(node->start, middle, node->value);
    node->right = new Node(middle + 1, node->end, node->value);
  }

  if (start <= middle) {
    updateAdd(start, min(middle, end), value, node->left);
  }
  if (end > middle) {
    updateAdd(max(middle + 1, start), end, value, node->right);
  }
  node->min_value = min(node->left->min_value, node->right->min_value);
  node->max_value = max(node->left->max_value, node->right->max_value);
}

void updateRemove(int start, int end, int value, Node *node) {
  //printf("[%d, %d] = %d", start, end, value);
  //printf("(%d %d %d %d %d %d)", node->start, node->end, node->min_value, node->max_value, node->left!=nullptr?1:0, node->right!=nullptr?1:0);
  if (start == node->start && end == node->end ) {
    if (node->min_value >= value) {
      node->SetValueForRange(value);
      return;
    }
    if (node->max_value <= value) {
      return;
    }
  }
  int middle = (node->start + node->end) / 2;

  if (node->left == nullptr) {
    node->left = new Node(node->start, middle, node->value);
    node->right = new Node(middle + 1, node->end, node->value);
  }

  if (start <= middle) {
    updateRemove(start, min(middle, end), value, node->left);
  }
  if (end > middle) {
    updateRemove(max(middle + 1, start), end, value, node->right);
  }
  node->min_value = min(node->left->min_value, node->right->min_value);
  node->max_value = max(node->left->max_value, node->right->max_value);
}

void PrintAll(Node *node, int finalHeight[])
{
  if (node->left == nullptr && node->right == nullptr)
  {
    for (int i = node->start; i <= node->end; i++)
    {
      finalHeight[i] = node->value;
    }
    return;
  }
  if (node->left != nullptr)
  {
    PrintAll(node->left, finalHeight);
  }
  if (node->right != nullptr)
  {
    PrintAll(node->right, finalHeight);
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  Node tree(0, n - 1, 0);
  for (int i = 0; i < k; i++)
  {
    if (op[i] == 1)
    {
      updateAdd(left[i], right[i], height[i], &tree);
    }
    else
    {
      updateRemove(left[i], right[i], height[i], &tree);
    }
  }
  PrintAll(&tree, finalHeight);
}

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