oj.uz

Submission #591858

# Submission time Handle Problem Language Result Execution time Memory
591858 2022-07-08T04:45:18 Z Shreyan_Paliwal Wall (IOI14_wall) C++17
100 / 100
 760 ms 69468 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)

const int INF  = 2000000000;
const int maxn = 2000000;
const int segn = (1 << 22);

int  seg[segn][2];
void addlower(int p, int l, int r, int k) {
  MAX(seg[p][0], k);
  MAX(seg[p][1], k);
}
void addupper(int p, int l, int r, int k) {
  MIN(seg[p][1], k);
  MIN(seg[p][0], seg[p][1]);
}
void push(int p, int l, int r) {
  if (seg[p][0] == seg[p][1] && seg[p][1] == INF) return;
  if (l == r) return;
  int mid = (l + r) >> 1;
  addlower((p << 1), l, mid, seg[p][0]);
  addlower((p << 1) | 1, mid + 1, r, seg[p][0]);

  addupper((p << 1), l, mid, seg[p][1]);
  addupper((p << 1) | 1, mid + 1, r, seg[p][1]);

  seg[p][0] = 0, seg[p][1] = INF;
}
void upd(int p, int l, int r, int L, int R, int K, char C) {
  push(p, l, r);
  if (r < L || R < l) return;
  if (L <= l && r <= R) {
    (C == 'L' ? addlower(p, l, r, K) : addupper(p, l, r, K));
    return;
  }
  int mid = (l + r) >> 1;
  upd(p << 1, l, mid, L, R, K, C);
  upd((p << 1) | 1, mid + 1, r, L, R, K, C);
}
void finalize(int p, int l, int r, int finalHeight[]) {
  push(p, l, r);
  if (l == r) {
    finalHeight[l] = seg[p][0];
    return;
  }
  int mid = (l + r) >> 1;
  finalize(p << 1, l, mid, finalHeight);
  finalize((p << 1) | 1, mid + 1, r, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  for (int i = 0; i < segn; i++) seg[i][0] = 0, seg[i][1] = INF;

  for (int i = 0; i < k; i++)
    if (op[i] == 1)
      upd(1, 0, n - 1, left[i], right[i], height[i], 'L');
    else
      upd(1, 0, n - 1, left[i], right[i], height[i], 'U');

  finalize(1, 0, n - 1, finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33028 KB Output is correct
2 Correct 17 ms 33252 KB Output is correct
3 Correct 16 ms 33192 KB Output is correct
4 Correct 20 ms 33356 KB Output is correct
5 Correct 19 ms 33348 KB Output is correct
6 Correct 23 ms 33328 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33028 KB Output is correct
2 Correct 133 ms 46748 KB Output is correct
3 Correct 190 ms 40216 KB Output is correct
4 Correct 504 ms 51104 KB Output is correct
5 Correct 331 ms 52168 KB Output is correct
6 Correct 333 ms 50560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33072 KB Output is correct
2 Correct 17 ms 33276 KB Output is correct
3 Correct 16 ms 33088 KB Output is correct
4 Correct 21 ms 33352 KB Output is correct
5 Correct 21 ms 33372 KB Output is correct
6 Correct 19 ms 33348 KB Output is correct
7 Correct 15 ms 33096 KB Output is correct
8 Correct 134 ms 46936 KB Output is correct
9 Correct 187 ms 40232 KB Output is correct
10 Correct 523 ms 51148 KB Output is correct
11 Correct 328 ms 52228 KB Output is correct
12 Correct 320 ms 50552 KB Output is correct
13 Correct 14 ms 33112 KB Output is correct
14 Correct 142 ms 46788 KB Output is correct
15 Correct 42 ms 34236 KB Output is correct
16 Correct 499 ms 51448 KB Output is correct
17 Correct 338 ms 50848 KB Output is correct
18 Correct 331 ms 50820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 16 ms 33256 KB Output is correct
3 Correct 17 ms 33112 KB Output is correct
4 Correct 21 ms 33348 KB Output is correct
5 Correct 19 ms 33348 KB Output is correct
6 Correct 20 ms 33364 KB Output is correct
7 Correct 15 ms 33044 KB Output is correct
8 Correct 132 ms 46748 KB Output is correct
9 Correct 185 ms 40296 KB Output is correct
10 Correct 488 ms 51100 KB Output is correct
11 Correct 329 ms 52216 KB Output is correct
12 Correct 334 ms 50660 KB Output is correct
13 Correct 14 ms 33108 KB Output is correct
14 Correct 135 ms 46844 KB Output is correct
15 Correct 42 ms 34304 KB Output is correct
16 Correct 503 ms 51360 KB Output is correct
17 Correct 337 ms 50784 KB Output is correct
18 Correct 322 ms 50804 KB Output is correct
19 Correct 760 ms 69468 KB Output is correct
20 Correct 738 ms 66992 KB Output is correct
21 Correct 752 ms 69464 KB Output is correct
22 Correct 743 ms 67040 KB Output is correct
23 Correct 732 ms 67080 KB Output is correct
24 Correct 739 ms 66944 KB Output is correct
25 Correct 732 ms 66928 KB Output is correct
26 Correct 749 ms 69468 KB Output is correct
27 Correct 750 ms 69452 KB Output is correct
28 Correct 730 ms 67036 KB Output is correct
29 Correct 750 ms 67040 KB Output is correct
30 Correct 738 ms 67132 KB Output is correct