oj.uz

Submission #424751

# Submission time Handle Problem Language Result Execution time Memory
424751 2021-06-12T09:38:59 Z priority_queue Wall (IOI14_wall) C++17
8 / 100
 3000 ms 9220 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 193 ms 1244 KB Output is correct
5 Correct 5 ms 944 KB Output is correct
6 Correct 5 ms 944 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 177 ms 9112 KB Output is correct
3 Execution timed out 3071 ms 6148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 195 ms 1192 KB Output is correct
5 Correct 5 ms 944 KB Output is correct
6 Correct 5 ms 940 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 152 ms 9220 KB Output is correct
9 Execution timed out 3091 ms 6244 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 197 ms 1176 KB Output is correct
5 Correct 5 ms 956 KB Output is correct
6 Correct 5 ms 912 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 161 ms 9100 KB Output is correct
9 Execution timed out 3071 ms 6080 KB Time limit exceeded
10 Halted 0 ms 0 KB -