제출 #979203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979203		kilkuwu	벽 (IOI14_wall)	C++17	100 / 100	877 ms	73692 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39