oj.uz

Submission #800502

# Submission time Handle Problem Language Result Execution time Memory
800502 2023-08-01T15:39:05 Z BERNARB01 Wall (IOI14_wall) C++17
100 / 100
 856 ms 65376 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif

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];

inline 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];

inline 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 5 ms 596 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 104 ms 8108 KB Output is correct
3 Correct 147 ms 4044 KB Output is correct
4 Correct 372 ms 10608 KB Output is correct
5 Correct 196 ms 11120 KB Output is correct
6 Correct 182 ms 11088 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 104 ms 8092 KB Output is correct
9 Correct 121 ms 3972 KB Output is correct
10 Correct 373 ms 10604 KB Output is correct
11 Correct 196 ms 11088 KB Output is correct
12 Correct 212 ms 11084 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 108 ms 8124 KB Output is correct
15 Correct 27 ms 1236 KB Output is correct
16 Correct 441 ms 10864 KB Output is correct
17 Correct 191 ms 10932 KB Output is correct
18 Correct 196 ms 10872 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 106 ms 8044 KB Output is correct
9 Correct 121 ms 4044 KB Output is correct
10 Correct 367 ms 10700 KB Output is correct
11 Correct 195 ms 11152 KB Output is correct
12 Correct 182 ms 11124 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 108 ms 8132 KB Output is correct
15 Correct 26 ms 1208 KB Output is correct
16 Correct 428 ms 10948 KB Output is correct
17 Correct 212 ms 10852 KB Output is correct
18 Correct 196 ms 10864 KB Output is correct
19 Correct 798 ms 65332 KB Output is correct
20 Correct 856 ms 62824 KB Output is correct
21 Correct 839 ms 65376 KB Output is correct
22 Correct 814 ms 62792 KB Output is correct
23 Correct 834 ms 62796 KB Output is correct
24 Correct 848 ms 62896 KB Output is correct
25 Correct 813 ms 62924 KB Output is correct
26 Correct 829 ms 65324 KB Output is correct
27 Correct 819 ms 65372 KB Output is correct
28 Correct 822 ms 62828 KB Output is correct
29 Correct 813 ms 62868 KB Output is correct
30 Correct 813 ms 62880 KB Output is correct