oj.uz

Submission #692252

# Submission time Handle Problem Language Result Execution time Memory
692252 2023-02-01T08:56:34 Z zeroesandones Wall (IOI14_wall) C++17
100 / 100
 1064 ms 59316 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

using ll = long long;
const int inf = 1e9 + 7;

struct node {
  int mn = 0, mx = inf;
};

struct SegTree {
  vector<node> tree;
  int n;

  SegTree(int N) {
    n = N;
    while(__builtin_popcountll(n) != 1) ++n;
    tree.resize(2 * n);
  }

  void prop(int v) {
    tree[2 * v].mn = min(tree[v].mx, max(tree[v * 2].mn, tree[v].mn));
    tree[2 * v].mx = max(tree[v].mn, min(tree[2 * v].mx, tree[v].mx));
    tree[2 * v + 1].mn = min(tree[v].mx, max(tree[v * 2 + 1].mn, tree[v].mn));
    tree[2 * v + 1].mx = max(tree[v].mn, min(tree[2 * v + 1].mx, tree[v].mx));
    tree[v].mn = 0;
    tree[v].mx = inf;
  }

  void update(int a, int b, int x, int y, int k, int v, int op) {
    if(a > y || b < x) return;
    if(a <= x && y <= b) {
      if(op == 1) {
        tree[k].mx = max(tree[k].mx, v);
        tree[k].mn = max(tree[k].mn, v);
      } else {
        tree[k].mx = min(tree[k].mx, v);
        tree[k].mn = min(tree[k].mn, v);
      }
      return;
    }

    prop(k);

    int d = (x + y) / 2;
    update(a, b, x, d, 2 * k, v, op);
    update(a, b, d + 1, y, 2 * k + 1, v, op);
  }

  void update(int a, int b, int v, int op) {
    update(a, b, 0, n - 1, 1, v, op);
  }

  int get(int x, int y, int k, int p) {
    if(x == y)
      return tree[k].mn;
    prop(k);

    int d = (x + y) / 2;
    if(p <= d)
      return get(x, d, 2 * k, p);
    return get(d + 1, y, 2 * k + 1, p);
  }

  int get(int p) {
    return get(0, n - 1, 1, p);
  }

  void print() {
    for(int i = 0; i < 2 * n; ++i) {
      cout << i << ' ' << tree[i].mn << ' ' << tree[i].mx << "\n";
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  SegTree sgt(n);

  for(int i = 0; i < k; ++i) {
    sgt.update(left[i], right[i], height[i], op[i]);
  }

  for(int i = 0; i < n; ++i) {
    finalHeight[i] = sgt.get(i);
  }
}

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 436 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 700 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 139 ms 13836 KB Output is correct
3 Correct 151 ms 7880 KB Output is correct
4 Correct 413 ms 20176 KB Output is correct
5 Correct 290 ms 20728 KB Output is correct
6 Correct 276 ms 19164 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 448 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 684 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 136 ms 13868 KB Output is correct
9 Correct 157 ms 7920 KB Output is correct
10 Correct 405 ms 20208 KB Output is correct
11 Correct 272 ms 20612 KB Output is correct
12 Correct 273 ms 19156 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 145 ms 13876 KB Output is correct
15 Correct 29 ms 1876 KB Output is correct
16 Correct 507 ms 20176 KB Output is correct
17 Correct 276 ms 19604 KB Output is correct
18 Correct 269 ms 19604 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 143 ms 13996 KB Output is correct
9 Correct 176 ms 7908 KB Output is correct
10 Correct 445 ms 20176 KB Output is correct
11 Correct 278 ms 20684 KB Output is correct
12 Correct 290 ms 19088 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 174 ms 13900 KB Output is correct
15 Correct 27 ms 1912 KB Output is correct
16 Correct 471 ms 20176 KB Output is correct
17 Correct 298 ms 19532 KB Output is correct
18 Correct 284 ms 19600 KB Output is correct
19 Correct 1064 ms 59228 KB Output is correct
20 Correct 945 ms 59208 KB Output is correct
21 Correct 957 ms 59156 KB Output is correct
22 Correct 876 ms 59212 KB Output is correct
23 Correct 1041 ms 59104 KB Output is correct
24 Correct 880 ms 59200 KB Output is correct
25 Correct 876 ms 59196 KB Output is correct
26 Correct 894 ms 59104 KB Output is correct
27 Correct 885 ms 59252 KB Output is correct
28 Correct 837 ms 59208 KB Output is correct
29 Correct 865 ms 59316 KB Output is correct
30 Correct 874 ms 59244 KB Output is correct