Submission #566040

#	Time	Username	Problem	Language	Result	Execution time	Memory
566040		elira	Wall (IOI14_wall)	C++14	8 / 100	3074 ms	13920 KiB

wall

#include "wall.h"


struct Node {

  Node(int start, int end, int value) {
    this->start = start;
    this->end = end;
    this->value = value;
  }

  int start, end;

  int 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 && node->left == nullptr && node->right == nullptr) {
    node->value = max(node->value, value);
    return;
  }
  int middle = (node->start + node->end) / 2;
  if (start <= middle) { // insert on the left
    if (node->left == nullptr) {
      node->left = new Node(node->start, middle, node->value);
      node ->right = new Node(middle+1, node->end, node->value);
    }
    updateAdd(start, min(middle, end), value, node->left);
  }
  if (end > middle) {
    if (node->right == nullptr) {
      node->left = new Node(node->start, middle, node->value);
      node ->right = new Node(middle+1, node->end, node->value);
    }
    updateAdd(max(middle+1, start), end, value, node->right);
  }
}

void updateRemove (int start, int end, int value, Node* node) {
  if (start == node->start && end == node->end && node->left == nullptr && node->right == nullptr) {
    node->value = min(node->value, value);
    return;
  }
  int middle = (node->start + node->end) / 2;
  if (start <= middle) { // insert on the left
    if (node->left == nullptr) {
      node->left = new Node(node->start, middle, node->value);
      node ->right = new Node(middle+1, node->end, node->value);
    }
    updateRemove(start, min(middle, end), value, node->left);
  }
  if (end > middle) {
    if (node->right == nullptr) {
      node->left = new Node(node->start, middle, node->value);
      node ->right = new Node(middle+1, node->end, node->value);
    }
    updateRemove(max(middle+1, start), end, value, node->right);
  }
}

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: 8 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39