oj.uz

Submission #577536

# Submission time Handle Problem Language Result Execution time Memory
577536 2022-06-15T04:03:36 Z Belgutei Wall (IOI14_wall) C++17
100 / 100
 761 ms 76460 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;
int level,zereg[30];
vector<int> add[30], rem[30];
int l,r;

void build() {
  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) {

    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(add[k + 1][x * 2] > rem[k][x]) add[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];
    if(add[k + 1][x * 2 + 1] > rem[k][x]) add[k + 1][x * 2 + 1] = rem[k][x];
    rem[k][x] = -1;
  }
  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;
}

int go(int pos) {
  int ret = 0;
  for(int i = level; i >= 0; i --) {
    if(rem[i][pos] != -1) if(ret > rem[i][pos]) ret = rem[i][pos];
    ret = max(ret, add[i][pos]);
    pos /= 2;
  }
  return ret;
} 

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

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n = N;
  build();
  for(int i = 0; i < k; i ++) {
    l = left[i];
    r = right[i];
    dfs(0,0,op[i],height[i]);
  }
  for(int i = 0; i < N; i ++) {
    finalHeight[i] = go(i);
  }
  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 852 KB Output is correct
5 Correct 5 ms 832 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 128 ms 8028 KB Output is correct
3 Correct 166 ms 4384 KB Output is correct
4 Correct 537 ms 11232 KB Output is correct
5 Correct 286 ms 21940 KB Output is correct
6 Correct 273 ms 20396 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 7 ms 852 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 13900 KB Output is correct
9 Correct 165 ms 8168 KB Output is correct
10 Correct 569 ms 20808 KB Output is correct
11 Correct 288 ms 21916 KB Output is correct
12 Correct 278 ms 20424 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 141 ms 13924 KB Output is correct
15 Correct 37 ms 2264 KB Output is correct
16 Correct 590 ms 21112 KB Output is correct
17 Correct 284 ms 20520 KB Output is correct
18 Correct 305 ms 20544 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 8 ms 828 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 13904 KB Output is correct
9 Correct 169 ms 8164 KB Output is correct
10 Correct 566 ms 20884 KB Output is correct
11 Correct 309 ms 21940 KB Output is correct
12 Correct 289 ms 20392 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 136 ms 13924 KB Output is correct
15 Correct 36 ms 2252 KB Output is correct
16 Correct 637 ms 21132 KB Output is correct
17 Correct 295 ms 20516 KB Output is correct
18 Correct 289 ms 20524 KB Output is correct
19 Correct 732 ms 76448 KB Output is correct
20 Correct 741 ms 73920 KB Output is correct
21 Correct 745 ms 76436 KB Output is correct
22 Correct 734 ms 73880 KB Output is correct
23 Correct 739 ms 74176 KB Output is correct
24 Correct 761 ms 74112 KB Output is correct
25 Correct 749 ms 73976 KB Output is correct
26 Correct 750 ms 76424 KB Output is correct
27 Correct 731 ms 76460 KB Output is correct
28 Correct 752 ms 74016 KB Output is correct
29 Correct 734 ms 74088 KB Output is correct
30 Correct 740 ms 74024 KB Output is correct