oj.uz

Submission #800500

# Submission time Handle Problem Language Result Execution time Memory
800500 2023-08-01T15:38:11 Z BERNARB01 Wall (IOI14_wall) C++17
100 / 100
 969 ms 75852 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 4e6 + 9;

struct node {
  int l = INT_MIN;
  int r = INT_MAX;

  void apply(int v, bool op) {
    if (op) {
      l = min(l, v);
      r = min(r, v);
    } else {
      l = max(l, v);
      r = max(r, v);
    }
  }
} tr[N];

void push(int x, int l, int r) {
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  if (tr[x].l != INT_MIN) {
    tr[x + 1].apply(tr[x].l, 0);
    tr[z].apply(tr[x].l, 0);
    tr[x].l = INT_MIN;
  }
  if (tr[x].r != INT_MAX) {
    tr[x + 1].apply(tr[x].r, 1);
    tr[z].apply(tr[x].r, 1);
    tr[x].r = INT_MAX;
  }
}

void modify(int x, int l, int r, int ll, int rr, int v, int op) {
  if (ll <= l && r <= rr) {
    tr[x].apply(v, op);
    return;
  }
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  push(x, l, r);
  if (ll <= y) {
    modify(x + 1, l, y, ll, rr, v, op);
  }
  if (rr > y) {
    modify(z, y + 1, r, ll, rr, v, op);
  }
}

int res[N];

void dfs(int x, int l, int r) {
  if (l == r) {
    res[l] = tr[x].l;
    return;
  }
  int y = (l + r) >> 1;
  int z = x + ((y - l + 1) << 1);
  push(x, l, r);
  dfs(x + 1, l, y);
  dfs(z, y + 1, r);
}

void buildWall(int n, int q, int op[], int ll[], int rr[], int h[], int finalHeight[]){
  for (int i = 0; i < n; i++) {
    modify(0, 0, n - 1, i, i, 0, 0);
    modify(0, 0, n - 1, i, i, 0, 1);
  }
  for (int i = 0; i < q; i++) {
    modify(0, 0, n - 1, ll[i], rr[i], h[i], op[i] - 1);
  }
  dfs(0, 0, n - 1);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = res[i];
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 112 ms 13872 KB Output is correct
3 Correct 127 ms 7816 KB Output is correct
4 Correct 392 ms 20308 KB Output is correct
5 Correct 240 ms 21268 KB Output is correct
6 Correct 198 ms 19780 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 131 ms 13900 KB Output is correct
9 Correct 126 ms 7808 KB Output is correct
10 Correct 398 ms 20208 KB Output is correct
11 Correct 212 ms 21392 KB Output is correct
12 Correct 201 ms 19684 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 117 ms 13984 KB Output is correct
15 Correct 27 ms 1768 KB Output is correct
16 Correct 439 ms 20544 KB Output is correct
17 Correct 220 ms 19968 KB Output is correct
18 Correct 206 ms 19952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 5 ms 712 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 131 ms 13876 KB Output is correct
9 Correct 126 ms 7820 KB Output is correct
10 Correct 394 ms 20208 KB Output is correct
11 Correct 210 ms 21396 KB Output is correct
12 Correct 199 ms 19744 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 121 ms 13928 KB Output is correct
15 Correct 27 ms 1732 KB Output is correct
16 Correct 439 ms 20468 KB Output is correct
17 Correct 211 ms 19900 KB Output is correct
18 Correct 206 ms 19976 KB Output is correct
19 Correct 920 ms 75736 KB Output is correct
20 Correct 918 ms 73260 KB Output is correct
21 Correct 960 ms 75816 KB Output is correct
22 Correct 916 ms 73240 KB Output is correct
23 Correct 923 ms 73308 KB Output is correct
24 Correct 942 ms 73324 KB Output is correct
25 Correct 892 ms 73268 KB Output is correct
26 Correct 907 ms 75800 KB Output is correct
27 Correct 915 ms 75852 KB Output is correct
28 Correct 969 ms 73212 KB Output is correct
29 Correct 919 ms 73272 KB Output is correct
30 Correct 968 ms 73264 KB Output is correct