oj.uz

Submission #566074

# Submission time Handle Problem Language Result Execution time Memory
566074 2022-05-21T18:06:44 Z elira Wall (IOI14_wall) C++14
100 / 100
 1074 ms 139340 KB 
#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;
      left = nullptr;
    if (right)
      delete right;
      right =nullptr;
  }

  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);
}

Compilation message

wall.cpp: In member function 'void Node::SetValueForRange(int)':
wall.cpp:32:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |     if (left)
      |     ^~
wall.cpp:34:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   34 |       left = nullptr;
      |       ^~~~
wall.cpp:35:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   35 |     if (right)
      |     ^~
wall.cpp:37:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |       right =nullptr;
      |       ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 560 KB Output is correct
5 Correct 6 ms 1256 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 141 ms 8344 KB Output is correct
3 Correct 190 ms 6236 KB Output is correct
4 Correct 711 ms 24256 KB Output is correct
5 Correct 271 ms 22980 KB Output is correct
6 Correct 268 ms 23028 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 524 KB Output is correct
5 Correct 5 ms 1196 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 141 ms 8884 KB Output is correct
9 Correct 176 ms 6220 KB Output is correct
10 Correct 737 ms 24284 KB Output is correct
11 Correct 274 ms 22948 KB Output is correct
12 Correct 262 ms 23044 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 147 ms 13824 KB Output is correct
15 Correct 61 ms 1572 KB Output is correct
16 Correct 1068 ms 15436 KB Output is correct
17 Correct 274 ms 22680 KB Output is correct
18 Correct 267 ms 22840 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 556 KB Output is correct
5 Correct 5 ms 1252 KB Output is correct
6 Correct 5 ms 1196 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 136 ms 8804 KB Output is correct
9 Correct 181 ms 6220 KB Output is correct
10 Correct 719 ms 24228 KB Output is correct
11 Correct 280 ms 22932 KB Output is correct
12 Correct 267 ms 23128 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 146 ms 13968 KB Output is correct
15 Correct 54 ms 1504 KB Output is correct
16 Correct 1074 ms 15568 KB Output is correct
17 Correct 271 ms 22664 KB Output is correct
18 Correct 261 ms 22676 KB Output is correct
19 Correct 824 ms 139052 KB Output is correct
20 Correct 792 ms 136512 KB Output is correct
21 Correct 796 ms 139340 KB Output is correct
22 Correct 788 ms 136728 KB Output is correct
23 Correct 800 ms 136792 KB Output is correct
24 Correct 797 ms 136788 KB Output is correct
25 Correct 790 ms 136736 KB Output is correct
26 Correct 828 ms 139320 KB Output is correct
27 Correct 803 ms 139204 KB Output is correct
28 Correct 796 ms 136652 KB Output is correct
29 Correct 803 ms 136732 KB Output is correct
30 Correct 797 ms 136800 KB Output is correct