oj.uz

Submission #555045

# Submission time Handle Problem Language Result Execution time Memory
555045 2022-04-30T03:29:42 Z Belgutei Wall (IOI14_wall) C++17
100 / 100
 794 ms 76612 KB 
#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

int n;

vector<int> add[30];
vector<int> rem[30];

int l,r;
int h, type;
int level,zereg[30];

void build_tree(){
  zereg[0] = 1;
  for(int i = 0; i <= 30; i++){
    if(zereg[i] >= n){
      level = i;
      break;
    }
    zereg[i + 1] = zereg[i] * 2;
  }
  for(int i = 0; i <= level; i++){
    for(int j = 0; j < zereg[i]; j++){
      add[i].pb(-1);
      rem[i].pb(-1);
    }
  }
}

void propogate(int k, int x){
  if(rem[k][x] != -1){
    add[k + 1][x * 2] = min(add[k + 1][x * 2], rem[k][x]);
    add[k + 1][x * 2 + 1] = min(add[k + 1][x * 2 +1], rem[k][x]);
    //
    if(rem[k + 1][x * 2] != -1) rem[k + 1][x * 2] = min(rem[k + 1][x * 2], rem[k][x]);
    else rem[k + 1][x * 2] = rem[k][x];
    //
    if(rem[k + 1][x * 2 + 1] != -1) rem[k + 1][x * 2 + 1] = min(rem[k + 1][x * 2 + 1], rem[k][x]);
    else rem[k + 1][x * 2 + 1] = rem[k][x];
  }
  add[k + 1][x * 2]= max(add[k + 1][x * 2], add[k][x]);
  add[k + 1][x * 2 + 1]= max(add[k + 1][x * 2 + 1], add[k][x]);
  add[k][x] = -1;
  rem[k][x] = -1;
}

void dfs(int k, int x){
  int y = zereg[level - k] * x;
  int z = zereg[level - k] * (x + 1) -1;;
  if(l <= y && z <= r){
    if(type == 1){
      if(add[k][x] < h) {
        add[k][x] = h;
      }
    }
    else{
      if(add[k][x] > h){
        add[k][x] = h;
      }
      if(rem[k][x] == -1) rem[k][x] = h;
      else if(rem[k][x] > h) rem[k][x] = h;
    }
    return;
  }
  if(z < l || y > r || k == level) return;
  propogate(k,x);
  dfs(k + 1, x * 2);
  dfs(k + 1, x * 2 + 1);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = N;
  build_tree();
  for(int i = 0; i < k; i++){
    l = left[i];
    r = right[i];
    h = height[i];
    type = op[i];
    dfs(0,0);
  }
  for(int i = 0; i < n; i++){
    int pos = i;
    for(int j = level; j >= 0; j--){
      if(rem[j][pos] != -1) finalHeight[i] = min(finalHeight[i], rem[j][pos]);
      finalHeight[i] = max(finalHeight[i], add[j][pos]);
      pos /= 2;
    }
  }
  return;
}

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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 6 ms 852 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 131 ms 8160 KB Output is correct
3 Correct 179 ms 4392 KB Output is correct
4 Correct 568 ms 20844 KB Output is correct
5 Correct 299 ms 21912 KB Output is correct
6 Correct 283 ms 20328 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 8 ms 852 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 134 ms 13892 KB Output is correct
9 Correct 172 ms 8196 KB Output is correct
10 Correct 551 ms 20824 KB Output is correct
11 Correct 296 ms 21956 KB Output is correct
12 Correct 281 ms 20428 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 146 ms 13868 KB Output is correct
15 Correct 35 ms 2152 KB Output is correct
16 Correct 612 ms 21088 KB Output is correct
17 Correct 296 ms 20604 KB Output is correct
18 Correct 297 ms 20616 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 6 ms 1020 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 140 ms 13972 KB Output is correct
9 Correct 172 ms 8272 KB Output is correct
10 Correct 563 ms 20964 KB Output is correct
11 Correct 289 ms 21980 KB Output is correct
12 Correct 284 ms 20344 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 141 ms 13868 KB Output is correct
15 Correct 35 ms 2264 KB Output is correct
16 Correct 608 ms 21180 KB Output is correct
17 Correct 295 ms 20644 KB Output is correct
18 Correct 290 ms 20576 KB Output is correct
19 Correct 743 ms 76500 KB Output is correct
20 Correct 741 ms 74068 KB Output is correct
21 Correct 751 ms 76452 KB Output is correct
22 Correct 754 ms 74060 KB Output is correct
23 Correct 756 ms 74096 KB Output is correct
24 Correct 754 ms 74032 KB Output is correct
25 Correct 783 ms 73896 KB Output is correct
26 Correct 764 ms 76612 KB Output is correct
27 Correct 794 ms 76584 KB Output is correct
28 Correct 753 ms 73888 KB Output is correct
29 Correct 791 ms 74012 KB Output is correct
30 Correct 764 ms 73976 KB Output is correct