제출 #424364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
424364		priority_queue	벽 (IOI14_wall)	C++14	8 / 100	3088 ms	13892 KiB

wall

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

using namespace std;

struct node {
 int left;
 int right;

 int left_child;
 int right_child;

 int height;
};

vector <node> memory;

void add(int n, int op, int left, int right, int height) {

  if (memory[n].left_child >= 0) {
    if (memory[memory[n].left_child].right < left) {
      add(memory[n].right_child, op, left, right, height);
    }
    else {
      if (memory[memory[n].left_child].right >= right) {
        add(memory[n].left_child, op, left, right, height);
      }
      else {
        add(memory[n].left_child, op, left, memory[memory[n].left_child].right, height);
        add(memory[n].right_child, op, memory[memory[n].right_child].left, right, height); 
      }
    }
  }
  else {
    if (memory[n].left == left && memory[n].right == right) {
      if (op == 1) {
        if (memory[n].height < height) {
          memory[n].height = height;
        }
      }
      else {
       if (memory[n].height > height) {
          memory[n].height = height;
        } 
      }
    }
    else {
      if (memory[n].left == left) {
        memory[n].left_child = memory.size();
        memory.push_back({left, right, -1, -1, memory[n].height});
        add(memory[n].left_child, op, left, right, height);

        memory[n].right_child = memory.size();
        memory.push_back({right+1, memory[n].right, -1, -1, memory[n].height});
      }
      else {
        memory[n].left_child = memory.size();
        memory.push_back({memory[n].left, left-1, -1, -1, memory[n].height});
        
        memory[n].right_child = memory.size();
        memory.push_back({left, memory[n].right, -1, -1, memory[n].height});
        add(memory[n].right_child, op, left, right, height);
      }
    }
  }
}

void fill_array(int n, int finalHeight[]) {
    if (memory[n].left_child >= 0) {
      fill_array(memory[n].left_child, finalHeight);
      fill_array(memory[n].right_child, finalHeight);
    }
    else {
      for(int i = memory[n].left; i <= memory[n].right; i++) {
        finalHeight[i] = memory[n].height;
      }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

  memory.push_back({0, n-1, -1, -1, 0});

  for(int i = 0; i < k; i++) {
    add(0, op[i], left[i], right[i], height[i]);
  }

  fill_array(0, finalHeight);

  return;
}

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