Submission #424751

#	Time	Username	Problem	Language	Result	Execution time	Memory
424751		priority_queue	Wall (IOI14_wall)	C++17	8 / 100	3091 ms	9220 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 {

            int mid = (memory[n].left + memory[n].right) / 2; 
            memory[n].left_child = memory.size();
            memory.push_back({memory[n].left, mid, -1, -1, memory[n].height});
      
            memory[n].right_child = memory.size();
            memory.push_back({mid+1, memory[n].right, -1, -1, memory[n].height});

            add(n, 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);
    for(int j=0; j<n; j++) {
        cerr << finalHeight[i] << " ";
    }
    cerr << endl;
    */
}

fill_array(0, finalHeight);

return;
}

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