test/verify/aoj-dsl-2-a.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_A

Depends on

Code

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

#include <algorithm>
#include <climits>
#include <iostream>

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

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  auto seg = SegmentTree(LambdaMonoid([](int a, int b) { return min(a, b); },
                                      []() { return INT_MAX; }),
                         N);
  while (Q--) {
    int T, X, Y;
    cin >> T >> X >> Y;
    if (T == 0)
      seg.set(X, Y);
    else
      cout << seg.prod(X, Y + 1) << "\n";
  }
}

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

#include <algorithm>
#include <climits>
#include <iostream>

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

#include <cassert>
#include <optional>
#include <vector>

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

template <typename S2, typename Op, typename E>
struct LambdaMonoid {
  using S = S2;
  S op(const S& a, const S& b) const { return _op(a, b); }

  S e() const { return _e(); }

  LambdaMonoid(Op _op, E _e) : _op(_op), _e(_e) {}

 private:
  Op _op;

  E _e;
};

template <typename Op, typename E>
LambdaMonoid(Op _op, E _e) -> LambdaMonoid<decltype(_e()), Op, E>;

/*
struct Monoid {
  using S = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
};
*/
#line 8 "structure/segment-tree/segment-tree.hpp"

template <typename Monoid>
struct SegmentTree {
  using S = typename Monoid::S;

 private:
  int n, sz;

  std::vector<S> seg;

  Monoid m;

 public:
  SegmentTree() = default;

  explicit SegmentTree(Monoid m, int n) : m(m), n(n) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, m.e());
  }

  explicit SegmentTree(Monoid m, const std::vector<S>& v)
      : SegmentTree(m, (int)v.size()) {
    build(v);
  }

  void build(const std::vector<S>& v) {
    assert(n == (int)v.size());
    for (int k = 0; k < n; k++) seg[k + sz] = v[k];
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void set(int k, const S& x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S get(int k) const { return seg[k + sz]; }

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

  void apply(int k, const S& x) {
    k += sz;
    seg[k] = m.op(seg[k], x);
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S prod(int l, int r) const {
    if (l >= r) return m.e();
    S L = m.e(), R = m.e();
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L = m.op(L, seg[l++]);
      if (r & 1) R = m.op(seg[--r], R);
    }
    return m.op(L, R);
  }

  S all_prod() const { return seg[1]; }

  template <typename C>
  std::optional<int> find_first(int l, const C& check) const {
    if (l >= n) return std::nullopt;
    l += sz;
    S sum = m.e();
    do {
      while ((l & 1) == 0) l >>= 1;
      if (check(m.op(sum, seg[l]))) {
        while (l < sz) {
          l <<= 1;
          auto nxt = m.op(sum, seg[l]);
          if (not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = m.op(sum, seg[l++]);
    } while ((l & -l) != l);
    return std::nullopt;
  }

  template <typename C>
  std::optional<int> find_last(int r, const C& check) const {
    if (r <= 0) return std::nullopt;
    r += sz;
    S sum = m.e();
    do {
      r--;
      while (r > 1 and (r & 1)) r >>= 1;
      if (check(m.op(seg[r], sum))) {
        while (r < sz) {
          r = (r << 1) + 1;
          auto nxt = m.op(seg[r], sum);
          if (not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = m.op(seg[r], sum);
    } while ((r & -r) != r);
    return std::nullopt;
  }
};
#line 10 "test/verify/aoj-dsl-2-a.test.cpp"

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  auto seg = SegmentTree(LambdaMonoid([](int a, int b) { return min(a, b); },
                                      []() { return INT_MAX; }),
                         N);
  while (Q--) {
    int T, X, Y;
    cin >> T >> X >> Y;
    if (T == 0)
      seg.set(X, Y);
    else
      cout << seg.prod(X, Y + 1) << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00	AC	2 ms	4 MB
g++	00_small_01	AC	2 ms	4 MB
g++	00_small_02	AC	2 ms	4 MB
g++	00_small_03	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	2 ms	4 MB
g++	02_biased_00	AC	2 ms	4 MB
g++	02_biased_01	AC	2 ms	4 MB
g++	02_biased_02	AC	2 ms	4 MB
g++	02_biased_03	AC	88 ms	4 MB
g++	03_rand_00	AC	3 ms	4 MB
g++	03_rand_01	AC	13 ms	4 MB
g++	03_rand_02	AC	13 ms	4 MB
g++	03_rand_03	AC	13 ms	4 MB
g++	03_rand_04	AC	108 ms	4 MB
g++	03_rand_05	AC	114 ms	4 MB
g++	04_maximum_00	AC	166 ms	4 MB
g++	04_maximum_01	AC	153 ms	4 MB
clang++	00_small_00	AC	2 ms	4 MB
clang++	00_small_01	AC	2 ms	4 MB
clang++	00_small_02	AC	2 ms	4 MB
clang++	00_small_03	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	2 ms	4 MB
clang++	02_biased_00	AC	2 ms	4 MB
clang++	02_biased_01	AC	2 ms	4 MB
clang++	02_biased_02	AC	2 ms	4 MB
clang++	02_biased_03	AC	88 ms	4 MB
clang++	03_rand_00	AC	3 ms	4 MB
clang++	03_rand_01	AC	13 ms	4 MB
clang++	03_rand_02	AC	13 ms	4 MB
clang++	03_rand_03	AC	20 ms	4 MB
clang++	03_rand_04	AC	109 ms	4 MB
clang++	03_rand_05	AC	105 ms	4 MB
clang++	04_maximum_00	AC	107 ms	4 MB
clang++	04_maximum_01	AC	108 ms	4 MB