test/verify/aoj-dsl-2-d.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 10:46:05+00:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D

Depends on

• structure/class/act.hpp
• Dual Segment Tree (双対セグメント木) (structure/segment-tree/dual-segment-tree.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
// clang-format on

#include <climits>
#include <iostream>

#include "../../structure/segment-tree/dual-segment-tree.hpp"

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  auto h = [](int, int b) { return b; };
  auto id = []() { return INT_MAX; };
  DualSegmentTree seg(LambdaAct(h, id), N);
  while (Q--) {
    int com;
    cin >> com;
    if (com == 0) {
      int l, r, x;
      cin >> l >> r >> x;
      seg.apply(l, r + 1, x);
    } else if (com == 1) {
      int k;
      cin >> k;
      cout << seg[k] << "\n";
    }
  }
}

#line 1 "test/verify/aoj-dsl-2-d.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
// clang-format on

#include <climits>
#include <iostream>

#line 2 "structure/segment-tree/dual-segment-tree.hpp"

#include <vector>

#line 2 "structure/class/act.hpp"

template <typename F2, typename Composition, typename Id>
struct LambdaAct {
  using F = F2;

  F composition(const F& f, const F& g) const { return _composition(f, g); }

  F id() const { return _id(); }

  LambdaAct(Composition _composition, Id _id)
      : _composition(_composition), _id(_id) {}

 private:
  Composition _composition;
  Id _id;
};

template <typename Composition, typename Id>
LambdaAct(Composition _composition, Id _id)
    -> LambdaAct<decltype(_id()), Composition, Id>;

/*
struct Act {
  using F = ?;
  static constexpr F composition(const F &f, const F &g) {}
  static constexpr F id() const {}
};
*/
#line 6 "structure/segment-tree/dual-segment-tree.hpp"

template <typename Act>
struct DualSegmentTree {
  using F = typename Act::F;

 private:
  int sz, height;
  std::vector<F> lazy;
  Act m;

  inline void propagate(int k) {
    if (lazy[k] != m.id()) {
      lazy[2 * k + 0] = m.composition(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = m.composition(lazy[2 * k + 1], lazy[k]);
      lazy[k] = m.id();
    }
  }

  inline void thrust(int k) {
    for (int i = height; i > 0; i--) propagate(k >> i);
  }

 public:
  DualSegmentTree(Act m, int n) : m(m) {
    sz = 1;
    height = 0;
    while (sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, m.id());
  }

  F get(int k) {
    thrust(k += sz);
    return lazy[k];
  }

  F operator[](int k) { return get(k); }

  void apply(int a, int b, const F& f) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) lazy[l] = m.composition(lazy[l], f), ++l;
      if (r & 1) --r, lazy[r] = m.composition(lazy[r], f);
    }
  }
};
#line 9 "test/verify/aoj-dsl-2-d.test.cpp"

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  auto h = [](int, int b) { return b; };
  auto id = []() { return INT_MAX; };
  DualSegmentTree seg(LambdaAct(h, id), N);
  while (Q--) {
    int com;
    cin >> com;
    if (com == 0) {
      int l, r, x;
      cin >> l >> r >> x;
      seg.apply(l, r + 1, x);
    } else if (com == 1) {
      int k;
      cin >> k;
      cout << seg[k] << "\n";
    }
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	2 ms	4 MB
g++	00_sample_01	AC	2 ms	4 MB
g++	01_rand_00	AC	2 ms	4 MB
g++	01_rand_01	AC	2 ms	4 MB
g++	01_rand_02	AC	2 ms	4 MB
g++	01_rand_03	AC	3 ms	4 MB
g++	01_rand_04	AC	5 ms	4 MB
g++	01_rand_05	AC	17 ms	4 MB
g++	02_corner_00	AC	2 ms	4 MB
g++	02_corner_01	AC	2 ms	4 MB
g++	03_large_00	AC	18 ms	4 MB
g++	03_large_01	AC	20 ms	4 MB
g++	03_large_02	AC	13 ms	4 MB
g++	03_large_03	AC	14 ms	4 MB
g++	04_maximum_00	AC	109 ms	4 MB
g++	04_maximum_01	AC	103 ms	4 MB
g++	04_maximum_02	AC	107 ms	4 MB
g++	04_maximum_03	AC	104 ms	4 MB
g++	05_critical_00	AC	97 ms	4 MB
g++	05_critical_01	AC	127 ms	4 MB
g++	05_critical_02	AC	56 ms	4 MB
g++	05_critical_03	AC	64 ms	4 MB
clang++	00_sample_00	AC	2 ms	4 MB
clang++	00_sample_01	AC	2 ms	4 MB
clang++	01_rand_00	AC	2 ms	4 MB
clang++	01_rand_01	AC	2 ms	4 MB
clang++	01_rand_02	AC	2 ms	4 MB
clang++	01_rand_03	AC	3 ms	4 MB
clang++	01_rand_04	AC	4 ms	4 MB
clang++	01_rand_05	AC	12 ms	4 MB
clang++	02_corner_00	AC	2 ms	4 MB
clang++	02_corner_01	AC	2 ms	4 MB
clang++	03_large_00	AC	13 ms	4 MB
clang++	03_large_01	AC	13 ms	4 MB
clang++	03_large_02	AC	12 ms	4 MB
clang++	03_large_03	AC	14 ms	4 MB
clang++	04_maximum_00	AC	120 ms	4 MB
clang++	04_maximum_01	AC	115 ms	4 MB
clang++	04_maximum_02	AC	107 ms	4 MB
clang++	04_maximum_03	AC	149 ms	4 MB
clang++	05_critical_00	AC	96 ms	4 MB
clang++	05_critical_01	AC	127 ms	4 MB
clang++	05_critical_02	AC	57 ms	4 MB
clang++	05_critical_03	AC	63 ms	4 MB

Back to top page