kyopro-lib

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: test/aoj/3118/main.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3118"

#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <vector>
#include "Mylib/Algorithm/sqrt_decomposition.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/IO/input_tuples.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  hl::sqrt_decomposition sd(N);

  auto [A, B] = hl::input_tuple_vector<int64_t, int64_t>(N);

  const int NUM = sd.block_num();

  std::vector<std::vector<int64_t>> s(NUM);
  std::vector<std::vector<int64_t>> left(NUM), right(NUM);
  std::vector<int64_t> sum(NUM);

  auto f =
      [&](int i, int l, int r) {
        const int size = r - l;

        std::vector<int64_t> d(size);
        for (int j = 0; j < size; ++j) d[j] = A[l + j] - B[l + j];

        std::vector<int> ord(size);
        std::iota(ord.begin(), ord.end(), 0);
        std::sort(ord.begin(), ord.end(), [&](int i_, int j_) { return d[i_] < d[j_]; });

        s[i].assign(size, 0);

        left[i].assign(size, 0);
        right[i].assign(size, 0);

        for (int j = 0; j < size; ++j) {
          s[i][j]     = d[ord[j]];
          left[i][j]  = B[l + ord[j]];
          right[i][j] = A[l + ord[j]];
        }

        for (int j = 1; j < size; ++j) {
          left[i][j] = std::min(left[i][j], left[i][j - 1]);
        }

        for (int j = size - 1; --j >= 0;) {
          right[i][j] = std::min(right[i][j], right[i][j + 1]);
        }
      };

  sd.init(f);

  for (auto [c] : hl::input_tuples<int>(Q)) {
    if (c == 1) {
      int l, r, x;
      std::cin >> l >> r >> x;
      --l;

      sd.query(
          l, r,
          [&](int i, int, int) {
            sum[i] += x;
          },
          [&](int i, int L, int R, int l, int r) {
            for (int j = L; j < R; ++j) A[j] += sum[i];
            for (int j = l; j < r; ++j) A[j] += x;
            sum[i] = 0;
            f(i, L, R);
          });
    } else {
      int l, r;
      std::cin >> l >> r;
      --l;

      int64_t ans = LLONG_MAX;

      sd.query(
          l, r,
          [&](int i, int L, int R) {
            int k = std::upper_bound(s[i].begin(), s[i].end(), -sum[i]) - s[i].begin();
            if (k - 1 >= 0) ans = std::min(ans, left[i][k - 1]);
            if (k < R - L) ans = std::min(ans, right[i][k] + sum[i]);
          },
          [&](int i, int, int, int l, int r) {
            for (int j = l; j < r; ++j) ans = std::min(ans, std::max(A[j] + sum[i], B[j]));
          });

      std::cout << ans << "\n";
    }
  }

  return 0;
}
#line 1 "test/aoj/3118/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3118"

#include <algorithm>
#include <climits>
#include <iostream>
#include <numeric>
#include <vector>
#line 3 "Mylib/Algorithm/sqrt_decomposition.cpp"
#include <cmath>

namespace haar_lib {
  class sqrt_decomposition {
    int N_, BLOCK_SIZE_, BLOCK_NUM_;

  public:
    sqrt_decomposition(int N) : N_(N), BLOCK_SIZE_((int) std::sqrt(N)), BLOCK_NUM_((N + BLOCK_SIZE_ - 1) / BLOCK_SIZE_) {}

    int block_size() const { return BLOCK_SIZE_; }
    int block_num() const { return BLOCK_NUM_; }

    template <typename Func>
    void init(const Func &f) {
      for (int i = 0; i < BLOCK_NUM_; ++i) {
        const int L = i * BLOCK_SIZE_;
        const int R = std::min<int>(N_, (i + 1) * BLOCK_SIZE_);
        f(i, L, R);
      }
    }

    template <typename FuncBlock, typename FuncRange>
    void query(int l, int r, const FuncBlock &func_block, const FuncRange &func_range) {
      for (int i = 0; i < BLOCK_NUM_; ++i) {
        const int L = i * BLOCK_SIZE_;
        const int R = std::min<int>(N_, (i + 1) * BLOCK_SIZE_);

        if (l <= L and R <= r) {
          func_block(i, L, R);
        } else if ((L <= l and l < R) or (L < r and r <= R)) {
          func_range(i, L, R, std::max(l, L), std::min(r, R));
        }
      }
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
  }

  template <typename T, size_t... I>
  void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
  }

  template <typename... Args>
  auto input_tuple_vector(int N) {
    std::tuple<std::vector<Args>...> ret;

    input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
    for (int i = 0; i < N; ++i) {
      input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
    }

    return ret;
  }
}  // namespace haar_lib
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 11 "test/aoj/3118/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  hl::sqrt_decomposition sd(N);

  auto [A, B] = hl::input_tuple_vector<int64_t, int64_t>(N);

  const int NUM = sd.block_num();

  std::vector<std::vector<int64_t>> s(NUM);
  std::vector<std::vector<int64_t>> left(NUM), right(NUM);
  std::vector<int64_t> sum(NUM);

  auto f =
      [&](int i, int l, int r) {
        const int size = r - l;

        std::vector<int64_t> d(size);
        for (int j = 0; j < size; ++j) d[j] = A[l + j] - B[l + j];

        std::vector<int> ord(size);
        std::iota(ord.begin(), ord.end(), 0);
        std::sort(ord.begin(), ord.end(), [&](int i_, int j_) { return d[i_] < d[j_]; });

        s[i].assign(size, 0);

        left[i].assign(size, 0);
        right[i].assign(size, 0);

        for (int j = 0; j < size; ++j) {
          s[i][j]     = d[ord[j]];
          left[i][j]  = B[l + ord[j]];
          right[i][j] = A[l + ord[j]];
        }

        for (int j = 1; j < size; ++j) {
          left[i][j] = std::min(left[i][j], left[i][j - 1]);
        }

        for (int j = size - 1; --j >= 0;) {
          right[i][j] = std::min(right[i][j], right[i][j + 1]);
        }
      };

  sd.init(f);

  for (auto [c] : hl::input_tuples<int>(Q)) {
    if (c == 1) {
      int l, r, x;
      std::cin >> l >> r >> x;
      --l;

      sd.query(
          l, r,
          [&](int i, int, int) {
            sum[i] += x;
          },
          [&](int i, int L, int R, int l, int r) {
            for (int j = L; j < R; ++j) A[j] += sum[i];
            for (int j = l; j < r; ++j) A[j] += x;
            sum[i] = 0;
            f(i, L, R);
          });
    } else {
      int l, r;
      std::cin >> l >> r;
      --l;

      int64_t ans = LLONG_MAX;

      sd.query(
          l, r,
          [&](int i, int L, int R) {
            int k = std::upper_bound(s[i].begin(), s[i].end(), -sum[i]) - s[i].begin();
            if (k - 1 >= 0) ans = std::min(ans, left[i][k - 1]);
            if (k < R - L) ans = std::min(ans, right[i][k] + sum[i]);
          },
          [&](int i, int, int, int l, int r) {
            for (int j = l; j < r; ++j) ans = std::min(ans, std::max(A[j] + sum[i], B[j]));
          });

      std::cout << ans << "\n";
    }
  }

  return 0;
}
Back to top page