oj.uz

Submission #979203

# Submission time Handle Problem Language Result Execution time Memory
979203 2024-05-10T11:36:43 Z kilkuwu Wall (IOI14_wall) C++17
100 / 100
 877 ms 73692 KB 
#include "wall.h"
#include <bits/stdc++.h>
template <typename T, typename L, typename F = std::plus<T>>
struct SegmentTree {
  int n;
  std::vector<T> tree;
  std::vector<L> lazy;

  SegmentTree(int _n) : n(_n), tree(2 * n - 1), lazy(2 * n - 1) {}

  template <typename Vec>
  void build(int x, int l, int r, const Vec& v) {
    if (l == r - 1) {
      tree[x] = T::from_value(v[l]);
      return;
    }

    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    build(y, l, m, v);
    build(z, m, r, v);
    tree[x] = F()(tree[y], tree[z]);
  } 

  template <typename Vec> 
  SegmentTree(const Vec& v) : SegmentTree(static_cast<int>(v.size())) {
    build(0, 0, n, v);
  }

  inline void apply(int x, const L& t) {
    tree[x].apply(t);
    lazy[x].apply(t);
  }

  inline void push(int x, int y, int z) {
    apply(y, lazy[x]);
    apply(z, lazy[x]);
    lazy[x] = L();
  }

  inline void pull(int x, int y, int z) {
    tree[x] = F()(tree[y], tree[z]);
  }

  void modify(int x, int l, int r, int p, const T& v) {
    if (l == r - 1) {
      tree[x] = v;
      return;
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (p < m)
      modify(y, l, m, p, v);
    else
      modify(z, m, r, p, v);
    pull(x, y, z);
  }

  void range_apply(int x, int l, int r, int ql, int qr, const L& t) {
    if (ql <= l && r <= qr) {
      apply(x, t);
      return;
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (m > ql) range_apply(y, l, m, ql, qr, t);
    if (m < qr) range_apply(z, m, r, ql, qr, t);
    pull(x, y, z);
  }

  T range_query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tree[x];
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (m <= ql) return range_query(z, m, r, ql, qr);
    if (m >= qr) return range_query(y, l, m, ql, qr);
    return F()(range_query(y, l, m, ql, qr), range_query(z, m, r, ql, qr));
  }

  inline void modify(int p, const T& v) {
    assert(0 <= p && p < n);
    modify(0, 0, n, p, v);
  }
  // NOTE: [l, r)
  inline void range_apply(int l, int r, const L& t) {
    assert(0 <= l && l < r && r <= n);
    range_apply(0, 0, n, l, r, t);
  }
  // NOTE: [l, r)
  inline T range_query(int l, int r) {
    assert(0 <= l && l < r && r <= n);
    return range_query(0, 0, n, l, r);
  }
};

struct Tag {
  int l = 0, r = 1e9; // make become this 
  
  inline void apply(const Tag& t) {
    if (t.l >= r) {
      l = t.l;
      r = t.l;
      return;
    } 
    if (t.r <= l) {
      l = t.r;
      r = t.r;
      return;
    }
    if (l < t.l) {
      l = t.l;
    }
    if (r > t.r) {
      r = t.r;
    }
  }
};

struct Info {
  int max_val = 0;

  inline void apply(const Tag& t) {
    if (max_val < t.l) {
      max_val = t.l;
    } 
    if (max_val > t.r) {
      max_val = t.r;
    }
  }

  friend Info operator+(const Info& l, const Info& r) {
    return {l.max_val < r.max_val ? r.max_val : l.max_val};
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
  
  SegmentTree<Info, Tag> tree(n);

  for (int i = 0; i < k; i++) {
    Tag val;
    if (op[i] == 1) {
      val.l = height[i];
    } else {
      val.r = height[i];
    }

    tree.range_apply(left[i], right[i] + 1, val);
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = tree.range_query(i, i + 1).max_val;
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 119 ms 13924 KB Output is correct
3 Correct 162 ms 6704 KB Output is correct
4 Correct 486 ms 20564 KB Output is correct
5 Correct 244 ms 21028 KB Output is correct
6 Correct 241 ms 19648 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 116 ms 13908 KB Output is correct
9 Correct 165 ms 7836 KB Output is correct
10 Correct 523 ms 20564 KB Output is correct
11 Correct 271 ms 21028 KB Output is correct
12 Correct 241 ms 19432 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 114 ms 13988 KB Output is correct
15 Correct 31 ms 1884 KB Output is correct
16 Correct 537 ms 20560 KB Output is correct
17 Correct 255 ms 19796 KB Output is correct
18 Correct 261 ms 20112 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 860 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 112 ms 13936 KB Output is correct
9 Correct 160 ms 7764 KB Output is correct
10 Correct 477 ms 20488 KB Output is correct
11 Correct 244 ms 21300 KB Output is correct
12 Correct 238 ms 19540 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 116 ms 13840 KB Output is correct
15 Correct 31 ms 1880 KB Output is correct
16 Correct 531 ms 20472 KB Output is correct
17 Correct 260 ms 20196 KB Output is correct
18 Correct 253 ms 19900 KB Output is correct
19 Correct 877 ms 73304 KB Output is correct
20 Correct 853 ms 73316 KB Output is correct
21 Correct 859 ms 73152 KB Output is correct
22 Correct 853 ms 73688 KB Output is correct
23 Correct 841 ms 73272 KB Output is correct
24 Correct 863 ms 73208 KB Output is correct
25 Correct 869 ms 73692 KB Output is correct
26 Correct 861 ms 73380 KB Output is correct
27 Correct 866 ms 73232 KB Output is correct
28 Correct 856 ms 73084 KB Output is correct
29 Correct 845 ms 73284 KB Output is correct
30 Correct 862 ms 73552 KB Output is correct