#740549 (C++17) No.1848 Long Prefixes

提出ソース
結果

問題	No.1848 Long Prefixes
ユーザー	risujiroh
提出日時	2022-02-18 23:08:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	24 ms / 2,000 ms
コード長	30,545 bytes
コンパイル時間	4,136 ms
コンパイル使用メモリ	337,980 KB
実行使用メモリ	7,424 KB
最終ジャッジ日時	2024-06-29 09:46:57
合計ジャッジ時間	5,909 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	24 ms 7,296 KB
testcase_01	AC	13 ms 7,296 KB
testcase_02	AC	12 ms 7,296 KB
testcase_03	AC	13 ms 7,424 KB
testcase_04	AC	11 ms 7,296 KB
testcase_05	AC	23 ms 7,168 KB
testcase_06	AC	13 ms 7,168 KB
testcase_07	AC	11 ms 7,168 KB
testcase_08	AC	13 ms 7,040 KB
testcase_09	AC	13 ms 7,168 KB
testcase_10	AC	21 ms 7,296 KB
testcase_11	AC	15 ms 7,168 KB
testcase_12	AC	12 ms 7,040 KB
testcase_13	AC	10 ms 7,040 KB
testcase_14	AC	13 ms 7,168 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	7 ms 5,376 KB
testcase_34	AC	10 ms 6,272 KB
testcase_35	AC	6 ms 5,376 KB
testcase_36	AC	6 ms 5,376 KB
testcase_37	AC	9 ms 5,760 KB
testcase_38	AC	8 ms 5,376 KB
testcase_39	AC	6 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if __INCLUDE_LEVEL__ == 0

#include __FILE__

void r7h::main(int) {
#define let auto const
  using fp = atcoder::modint1000000007;
  let n = input();
  let a = input<vla<int>>(n);
  let s = input<string>();

  vector<pair<char, int>> v(n - 1);
  for (let i : rep(1, n)) { v[i - 1] = {s[i], a[i]}; }
  let za = atcoder::z_algorithm(v);

  let suff = reversed(a).scan(fp(0)).to_vla(true);

  fp ans = suff[0] + a[0] * fp(a[0] - 1) / 2;
  for (let i : rep(1, n).filter(LAMBDA(s[_1] == s[0]))) {
    if (a[0] <= a[i]) {
      ans += a[0] * fp(a[i] - a[0]) + a[0] * fp(a[0] + 1) / 2;
      if (i + 1 < n && za[i]) {
        ans += suff[i + 1] - suff[i + za[i] + 1];
        if (i + za[i] + 1 < n && s[i + za[i] + 1] == s[za[i] + 1]) { ans += min(a[i + za[i] + 1], a[za[i] + 1]); }
      } else if (i + 1 < n && s[i + 1] == s[1]) {
        ans += min(a[i + 1], a[1]);
      }
    } else {
      ans += a[i] * fp(a[i] + 1) / 2;
    }
  }
  println(ans.val());
}

#else

#define MULTI_CASES 0
#define INTERACTIVE 0
#define USE_INT 1

#ifndef LOCAL
#define LOCAL 0
#endif

#if !LOCAL
#define NDEBUG
#endif

#ifndef __GLIBCXX_TYPE_INT_N_0
#define __GLIBCXX_TYPE_INT_N_0 __int128
#endif

#include <bits/stdc++.h>
#include <unistd.h>
#include <x86intrin.h>

namespace r7h {

using namespace std;

void main(int);

}  // namespace r7h

#if LOCAL
#include <utility/dump.hpp>
#else
#define DUMP(...) void(0)
#endif

#define LIFT(FN) \
  []<class... Ts_>(Ts_&&... xs_) -> decltype(auto) { return FN(static_cast<Ts_&&>(xs_)...); }

#define LAMBDA(...) \
  [&]<class T1_ = void*, class T2_ = void*>([[maybe_unused]] T1_&& _1 = nullptr, [[maybe_unused]] T2_&& _2 = nullptr) \
      -> decltype(auto) { \
    return __VA_ARGS__; \
  }

namespace r7h {

template <class F>
class fix : F {
 public:
  explicit fix(F f) : F(move(f)) {}

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) const {
    return F::operator()(ref(*this), forward<Ts>(xs)...);
  }
};

template <class T>
decay_t<T> decay_copy(T&& x) {
  return forward<T>(x);
}

template <class T>
auto ref_or_move(remove_reference_t<T>& x) {
  if constexpr (is_reference_v<T> && !is_placeholder_v<decay_t<T>>) {
    return ref(x);
  } else {
    return move(x);
  }
}

template <class T, class D = decay_t<T>>
bool const is_lambda_expr = is_placeholder_v<D> || is_bind_expression_v<D>;

#define UNARY_LAMBDA(OP) \
  template <class T, enable_if_t<is_lambda_expr<T>>* = nullptr> \
  auto operator OP(T&& x) { \
    return bind([]<class T_>(T_&& x_) -> decltype(auto) { return OP forward<T_>(x_); }, ref_or_move<T>(x)); \
  }

#define BINARY_LAMBDA(OP) \
  template <class T1, class T2, enable_if_t<is_lambda_expr<T1> || is_lambda_expr<T2>>* = nullptr> \
  auto operator OP(T1&& x, T2&& y) { \
    return bind( \
        []<class T1_, class T2_>(T1_&& x_, T2_&& y_) -> decltype(auto) { return forward<T1_>(x_) OP forward<T2_>(y_); }, \
        ref_or_move<T1>(x), ref_or_move<T2>(y)); \
  }

BINARY_LAMBDA(+=)
BINARY_LAMBDA(-=)
BINARY_LAMBDA(*=)
BINARY_LAMBDA(/=)
BINARY_LAMBDA(%=)
BINARY_LAMBDA(&=)
BINARY_LAMBDA(|=)
BINARY_LAMBDA(^=)
BINARY_LAMBDA(<<=)
BINARY_LAMBDA(>>=)

UNARY_LAMBDA(++)
UNARY_LAMBDA(--)

UNARY_LAMBDA(+)
UNARY_LAMBDA(-)
BINARY_LAMBDA(+)
BINARY_LAMBDA(-)
BINARY_LAMBDA(*)
BINARY_LAMBDA(/)
BINARY_LAMBDA(%)

UNARY_LAMBDA(~)
BINARY_LAMBDA(&)
BINARY_LAMBDA(|)
BINARY_LAMBDA(^)
BINARY_LAMBDA(<<)
BINARY_LAMBDA(>>)

BINARY_LAMBDA(==)
BINARY_LAMBDA(!=)
BINARY_LAMBDA(<)
BINARY_LAMBDA(>)
BINARY_LAMBDA(<=)
BINARY_LAMBDA(>=)

UNARY_LAMBDA(!)
BINARY_LAMBDA(&&)
BINARY_LAMBDA(||)

#undef UNARY_LAMBDA
#undef BINARY_LAMBDA

using namespace placeholders;

namespace scan_impl {

#if INTERACTIVE || LOCAL

bool scan(char& c) { return scanf(" %c", &c) != EOF; }

bool scan(string& s) {
  char c;
  if (!scan(c)) { return false; }
  for (s = c;; s += c) {
    c = char(getchar());
    if (c <= ' ') {
      ungetc(c, stdin);
      break;
    }
  }
  return true;
}

template <class T>
enable_if_t<is_integral_v<T>, bool> scan(T& x) {
  char c;
  if (!scan(c)) { return false; }
  make_unsigned_t<common_type_t<T, int>> u = (c == '-' ? getchar() : c) & 15;
  while (true) {
    if (int t = getchar(); '0' <= t && t <= '9') {
      (u *= 10) += t & 15;
    } else {
      ungetc(t, stdin);
      break;
    }
  }
  x = T(c == '-' ? -u : u);
  return true;
}

template <class T>
enable_if_t<is_floating_point_v<T>, bool> scan(T& x) {
  return scanf(is_same_v<T, float> ? "%f" : is_same_v<T, double> ? "%lf" : "%Lf", &x) != EOF;
}

#else

char buf[1 << 15];
char* ptr = buf;
char* last = buf;

bool scan(char& c) {
  for (;; ++ptr) {
    if (last - ptr < 64) {
      last = move(ptr, last, buf);
      ptr = buf;
      last += read(STDIN_FILENO, last, end(buf) - last - 1);
      *last = '\0';
    }
    if (ptr == last) { return false; }
    if (' ' < *ptr) {
      c = *ptr++;
      return true;
    }
  }
}

bool scan(string& s) {
  char c;
  if (!scan(c)) { return false; }
  for (s = c; ' ' < *ptr; s += c) { scan(c); }
  return true;
}

template <class T>
enable_if_t<is_integral_v<T>, bool> scan(T& x) {
  char c;
  if (!scan(c)) { return false; }
  make_unsigned_t<common_type_t<T, int>> u = (c == '-' ? *ptr++ : c) & 15;
  while ('0' <= *ptr && *ptr <= '9') { (u *= 10) += *ptr++ & 15; }
  x = T(c == '-' ? -u : u);
  return true;
}

template <class T>
enable_if_t<is_floating_point_v<T>, bool> scan(T& x) {
  char c;
  if (!scan(c)) { return false; }
  int n;
  sscanf(--ptr, is_same_v<T, float> ? "%f%n" : is_same_v<T, double> ? "%lf%n" : "%Lf%n", &x, &n);
  ptr += n;
  return true;
}

#endif

template <class R>
auto scan(R&& r) -> decltype(begin(r), end(r), true) {
  return all_of(begin(r), end(r), LIFT(scan));
}

template <class... Ts>
enable_if_t<sizeof...(Ts) != 1, bool> scan(Ts&&... xs) {
  return (... && scan(forward<Ts>(xs)));
}

}  // namespace scan_impl

using scan_impl::scan;

template <class T = int, class... Args>
T input(Args&&... args) {
  T ret(forward<Args>(args)...);
  [[maybe_unused]] bool res = scan(ret);
  assert(res);
  return ret;
}

namespace print_impl {

#if INTERACTIVE || LOCAL

template <char = 0>
void print(char c) {
  if (c) { putchar(c); }
  if (c == '\n') { fflush(stdout); }
}

template <char = 0, class T>
enable_if_t<is_integral_v<T>> print(T x) {
  char buf[64];
  char* ptr = to_chars(buf, end(buf), x).ptr;
  for_each(buf, ptr, LIFT(print));
}

template <char = 0, class T>
enable_if_t<is_floating_point_v<T>> print(T x) {
  printf(is_same_v<T, float> ? "%.6f" : is_same_v<T, double> ? "%.15f" : "%.18Lf", x);
}

#else

char buf[1 << 15];
char* ptr = buf;

__attribute__((destructor)) void flush() {
  if (write(STDOUT_FILENO, buf, ptr - buf) == -1) { abort(); }
  ptr = buf;
}

template <char = 0>
void print(char c) {
  if (end(buf) - ptr < 64) { flush(); }
  if (c) { *ptr++ = c; }
}

template <char = 0, class T>
enable_if_t<is_integral_v<T>> print(T x) {
  print('\0');
  ptr = to_chars(ptr, end(buf), x).ptr;
}

template <char = 0, class T>
enable_if_t<is_floating_point_v<T>> print(T x) {
  print('\0');
  ptr += snprintf(ptr, end(buf) - ptr, is_same_v<T, float> ? "%.6f" : is_same_v<T, double> ? "%.15f" : "%.18Lf", x);
}

#endif

template <char Sep = ' ', class R>
auto print(R&& r) -> void_t<decltype(begin(r), end(r))> {
  [[maybe_unused]] char c = '\0';
  for (auto&& e : r) {
    if constexpr (!is_same_v<decay_t<decltype(e)>, char>) { print(exchange(c, Sep)); }
    print(e);
  }
}

template <char = 0>
void print(char const* s) {
  print(string_view(s));
}

template <char Sep = ' ', class... Ts>
enable_if_t<sizeof...(Ts) != 1> print(Ts&&... xs) {
  [[maybe_unused]] char c = '\0';
  (..., (print(exchange(c, Sep)), print(forward<Ts>(xs))));
}

}  // namespace print_impl

using print_impl::print;

template <char Sep = ' ', char End = '\n', class... Ts>
void println(Ts&&... xs) {
  print<Sep>(forward<Ts>(xs)...);
  print(End);
}

#if USE_INT
using ptrdiff_t = int;
#endif

using i8 = signed char;
using u8 = unsigned char;
using i16 = short;
using u16 = unsigned short;
using i32 = int;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;

template <int> struct signed_int;
template <int> struct unsigned_int;

#define INT_TYPE(N) \
  template <> struct signed_int<N> { using type = i##N; }; \
  template <> struct unsigned_int<N> { using type = u##N; };

INT_TYPE(8)
INT_TYPE(16)
INT_TYPE(32)
INT_TYPE(64)
INT_TYPE(128)

#undef INT_TYPE

template <int N> using signed_int_t = typename signed_int<N>::type;
template <int N> using unsigned_int_t = typename unsigned_int<N>::type;

template <class T, int D = 1>
class vla {
  static_assert(1 <= D);

  array<ptrdiff_t, D> len;
  T* dat;

 public:
  vla() = default;
  explicit vla(array<ptrdiff_t, D> n) : len(n) {
    partial_sum(rbegin(len), rend(len), rbegin(len), multiplies());
    dat = new T[len[0]];
  }
  explicit vla(array<ptrdiff_t, D> n, T const& val) : vla(n) { fill_n(dat, len[0], val); }
  vla(vla const& x) : len(x.len), dat(new T[len[0]]) { copy_n(x.dat, len[0], dat); }
  vla(vla&& x) noexcept : vla() { *this = move(x); }

  template <int D_ = D, enable_if_t<D_ == 1>* = nullptr>
  explicit vla(ptrdiff_t n) : vla(array{n}) {}

  template <int D_ = D, enable_if_t<D_ == 1>* = nullptr>
  explicit vla(ptrdiff_t n, T const& val) : vla(array{n}, val) {}

  vla& operator=(vla const& x) & { return *this = vla(x); }
  vla& operator=(vla&& x) & noexcept {
    swap(len, x.len);
    swap(dat, x.dat);
    return *this;
  }

  ~vla() { delete[] dat; }

  bool check(ptrdiff_t i) const { return 0 <= i && i < len[0]; }
  T& operator[](ptrdiff_t i) & {
    assert(check(i));
    return dat[i];
  }
  T const& operator[](ptrdiff_t i) const& {
    assert(check(i));
    return dat[i];
  }
  T operator[](ptrdiff_t i) && {
    assert(check(i));
    return move(dat[i]);
  }

  bool check(array<ptrdiff_t, D> i) const {
    for (int d = 0; d + 1 < D; ++d) {
      if (i[d] < 0) { return false; }
      if (len[d] <= i[d] * len[d + 1]) { return false; }
    }
    return 0 <= i.back() && i.back() < len.back();
  }
  ptrdiff_t flatten(array<ptrdiff_t, D> i) const {
    assert(check(i));
    return inner_product(i.begin(), i.end() - 1, len.begin() + 1, i.back());
  }
  T& operator[](array<ptrdiff_t, D> i) & { return dat[flatten(i)]; }
  T const& operator[](array<ptrdiff_t, D> i) const& { return dat[flatten(i)]; }
  T operator[](array<ptrdiff_t, D> i) && { return move(dat[flatten(i)]); }

  T* begin() & { return dat; }
  T const* begin() const& { return dat; }
  T* end() & { return dat + len[0]; }
  T const* end() const& { return dat + len[0]; }
  ptrdiff_t size() const { return len[0]; }
};

template <class T>
auto operator++(T& x, int) -> decltype(++x, T(x)) {
  T ret = x;
  ++x;
  return ret;
}

template <class T>
auto operator--(T& x, int) -> decltype(--x, T(x)) {
  T ret = x;
  --x;
  return ret;
}

#define BINARY_ARITH_OP(OP) \
  template <class T1, class T2, class T = common_type_t<T1, T2>> \
  auto operator OP(T1 const& x, T2 const& y) -> decltype(declval<T&>() OP##= y, T(x)) { \
    T ret = T(x); \
    ret OP##= y; \
    return ret; \
  }

BINARY_ARITH_OP(+)
BINARY_ARITH_OP(-)
BINARY_ARITH_OP(*)
BINARY_ARITH_OP(/)
BINARY_ARITH_OP(%)
BINARY_ARITH_OP(&)
BINARY_ARITH_OP(|)
BINARY_ARITH_OP(^)
BINARY_ARITH_OP(<<)
BINARY_ARITH_OP(>>)

#undef BINARY_ARITH_OP

#define COMPARISON_OP(OP, E) \
  template <class T1, class T2> \
  auto operator OP(T1 const& x, T2 const& y) -> decltype(E) { \
    return E; \
  }

COMPARISON_OP(!=, !(x == y))
COMPARISON_OP(>, y < x)
COMPARISON_OP(<=, !(y < x))
COMPARISON_OP(>=, !(x < y))

#undef COMPARISON_OP

template <class D, class C, class R>
class iter_base {
  D& derived() & { return static_cast<D&>(*this); }
  D const& derived() const& { return static_cast<D const&>(*this); }
  bool equal(D const& x) const { return derived().equal(x); }
  ptrdiff_t dist_to(D const& x) const { return derived().dist_to(x); }

 public:
  using iterator_category = C;
  using value_type = decay_t<R>;
  using difference_type = ptrdiff_t;
  using pointer = void;
  using reference = R;

#define REQUIRE(CATEGORY) template <class C_ = C, enable_if_t<is_convertible_v<C_, CATEGORY##_iterator_tag>>* = nullptr>

  R operator*() const { return derived().deref(); }
  REQUIRE(random_access) R operator[](ptrdiff_t n) const { return *(derived() + n); }

  D& operator++() & {
    derived().inc();
    return derived();
  }
  REQUIRE(bidirectional) D& operator--() & {
    derived().dec();
    return derived();
  }
  REQUIRE(random_access) D& operator+=(ptrdiff_t n) & {
    derived().advance(n);
    return derived();
  }
  REQUIRE(random_access) D& operator-=(ptrdiff_t n) & {
    derived().advance(-n);
    return derived();
  }

  REQUIRE(random_access) friend D operator+(D const& x, ptrdiff_t n) {
    D ret = x;
    ret += n;
    return ret;
  }
  REQUIRE(random_access) friend D operator+(ptrdiff_t n, D const& x) { return x + n; }
  REQUIRE(random_access) friend D operator-(D const& x, ptrdiff_t n) {
    D ret = x;
    ret -= n;
    return ret;
  }
  REQUIRE(random_access) friend ptrdiff_t operator-(D const& x, D const& y) {
    return static_cast<iter_base const&>(y).dist_to(x);
  }

  friend bool operator==(D const& x, D const& y) { return static_cast<iter_base const&>(x).equal(y); }
  REQUIRE(random_access) friend bool operator<(D const& x, D const& y) { return x - y < 0; }

#undef REQUIRE
};

template <class T>
class int_iter : public iter_base<int_iter<T>, random_access_iterator_tag, T> {
  friend class int_iter::iter_base;

  T v;

  T deref() const { return v; }
  bool equal(int_iter const& x) const { return v == x.v; }
  void inc() & { ++v; }
  void dec() & { --v; }
  void advance(ptrdiff_t n) & { v += T(n); }
  ptrdiff_t dist_to(int_iter const& x) const { return make_signed_t<T>(x.v - v); }

 public:
  int_iter() = default;
  explicit int_iter(T v) : v(v) {}
};

template <class R>
auto sz(R&& r) -> decltype(ptrdiff_t(size(forward<R>(r)))) {
  return ptrdiff_t(size(forward<R>(r)));
}

template <class T>
T div_floor(T x, T y) {
  return T(x / y - ((x ^ y) < 0 && x % y));
}

template <class T>
T div_ceil(T x, T y) {
  return T(x / y + (0 <= (x ^ y) && x % y));
}

template <class T, class U = T>
bool chmin(T& x, U&& y) {
  return y < x ? x = forward<U>(y), true : false;
}

template <class T, class U = T>
bool chmax(T& x, U&& y) {
  return x < y ? x = forward<U>(y), true : false;
}

template <class T>
T const inf_v = numeric_limits<T>::max() / 2;

int const inf = inf_v<int>;

mt19937_64 mt(_rdtsc());

template <class T>
T rand(T a, T b) {
  if constexpr (is_integral_v<T>) {
    return uniform_int_distribution(a, b)(mt);
  } else {
    return uniform_real_distribution(a, b)(mt);
  }
}

#define TC(...) template <class __VA_ARGS__>

TC(R) using iter_t = decltype(begin(declval<R const&>()));
TC(R) using range_cat = typename iterator_traits<iter_t<R>>::iterator_category;
TC(R) using range_ref = typename iterator_traits<iter_t<R>>::reference;

TC() class view_base;

#define Z ptrdiff_t
#define IIT input_iterator_tag
#define FIT forward_iterator_tag
#define BIT bidirectional_iterator_tag
#define RAIT random_access_iterator_tag
#define VIEW(CLS, ...) \
  class CLS : public view_base<CLS<__VA_ARGS__>> { \
    friend class CLS::view_base;
#define VIEW_END(...) \
  __VA_OPT__(Z size() const { return __VA_ARGS__; }) \
  };

TC(R, class F)
VIEW(filtered, R, F)
  struct iter : iter_base<iter, common_type_t<range_cat<R>, BIT>, range_ref<R>> {
    filtered const* p;
    iter_t<R> i;
    range_ref<R> deref() const { return *i; }
    bool equal(iter const& x) const { return i == x.i; }
    void inc() & {
      do { ++i; } while (i != end(p->r) && !invoke(p->f, *i));
    }
    void dec() & {
      do { --i; } while (!invoke(p->f, *i));
    }
  };

  R r;
  [[no_unique_address]] F f;

  iter b() const { return {{}, this, find_if(begin(r), end(r), ref(f))}; }
  iter e() const { return {{}, this, end(r)}; }

 public:
  explicit filtered(R&& r, F f) : r(forward<R>(r)), f(move(f)) {}
VIEW_END()

TC(R, class F) filtered(R&&, F) -> filtered<R, F>;

TC(R, class F)
VIEW(mapped, R, F)
  using ref = invoke_result_t<F const&, range_ref<R>>;

  struct iter : iter_base<iter, common_type_t<range_cat<R>, RAIT>, ref> {
    mapped const* p;
    iter_t<R> i;
    ref deref() const { return invoke(p->f, *i); }
    bool equal(iter const& x) const { return i == x.i; }
    void inc() & { ++i; }
    void dec() & { --i; }
    void advance(Z n) & { i += n; }
    Z dist_to(iter const& x) const { return Z(x.i - i); }
  };

  R r;
  [[no_unique_address]] F f;

  iter b() const { return {{}, this, begin(r)}; }
  iter e() const { return {{}, this, end(r)}; }

 public:
  explicit mapped(R&& r, F f) : r(forward<R>(r)), f(move(f)) {}
VIEW_END(sz(r))

TC(R, class F) mapped(R&&, F) -> mapped<R, F>;

TC(R)
VIEW(taken, R)
  struct iter : iter_base<iter, common_type_t<range_cat<R>, FIT>, range_ref<R>> {
    iter_t<R> i;
    Z n;
    range_ref<R> deref() const { return *i; }
    bool equal(iter const& x) const { return n == x.n; }
    void inc() & {
      --n;
      if (n) { ++i; }
    }
  };

  R r;
  Z n;

  auto b() const {
    if constexpr (is_convertible_v<range_cat<R>, RAIT>) {
      return begin(r);
    } else {
      return iter{{}, n ? begin(r) : end(r), n};
    }
  }
  auto e() const {
    if constexpr (is_convertible_v<range_cat<R>, RAIT>) {
      return begin(r) + size();
    } else {
      return iter{{}, end(r), 0};
    }
  }

 public:
  explicit taken(R&& r, Z n) : r(forward<R>(r)), n(max<Z>(n, 0)) { assert(0 <= n); }
VIEW_END(min(n, sz(r)))

TC(R) taken(R&&, Z) -> taken<R>;

TC(R, class F)
VIEW(taken_while, R, F)
  static_assert(is_convertible_v<range_cat<R>, FIT>);

  struct iter : iter_base<iter, common_type_t<range_cat<R>, FIT>, range_ref<R>> {
    taken_while const* p;
    iter_t<R> i;
    range_ref<R> deref() const { return *i; }
    bool equal(iter const& x) const { return i == x.i; }
    void inc() & {
      ++i;
      if (i != end(p->r) && !invoke(p->f, *i)) { i = end(p->r); }
    }
  };

  R r;
  [[no_unique_address]] F f;

  iter b() const { return {{}, this, begin(r) == end(r) || !invoke(f, *begin(r)) ? end(r) : begin(r)}; }
  iter e() const { return {{}, this, end(r)}; }

 public:
  explicit taken_while(R&& r, F f) : r(forward<R>(r)), f(move(f)) {}
VIEW_END()

TC(R, class F) taken_while(R&&, F) -> taken_while<R, F>;

TC(R)
VIEW(dropped, R)
  R r;
  Z n;

  auto b() const {
    if constexpr (is_convertible_v<range_cat<R>, RAIT>) {
      return begin(r) + min(n, sz(r));
    } else {
      auto ret = begin(r);
      for (Z _ = n; _-- && ret != end(r);) { ++ret; }
      return ret;
    }
  }
  auto e() const { return end(r); }

 public:
  explicit dropped(R&& r, Z n) : r(forward<R>(r)), n(max<Z>(n, 0)) { assert(0 <= n); }
VIEW_END(max(sz(r), n) - n)

TC(R) dropped(R&&, Z) -> dropped<R>;

TC(R, class F)
VIEW(dropped_while, R, F)
  R r;
  [[no_unique_address]] F f;

  auto b() const { return find_if_not(begin(r), end(r), ref(f)); }
  auto e() const { return end(r); }

 public:
  explicit dropped_while(R&& r, F f) : r(forward<R>(r)), f(move(f)) {}
VIEW_END()

TC(R, class F) dropped_while(R&&, F) -> dropped_while<R, F>;

TC(R)
VIEW(joined, R)
  using IR = range_ref<R>;
  static_assert(is_convertible_v<range_cat<R>, FIT> && is_convertible_v<range_cat<IR>, FIT>);

  struct iter : iter_base<iter, common_type<range_cat<R>, range_cat<IR>, FIT>, range_ref<IR>> {
    joined const* p;
    iter_t<R> o;
    iter_t<IR> i;
    range_ref<IR> deref() const { return *i; }
    bool equal(iter const& x) const { return o == x.o && i == x.i; }
    void inc() & {
      for (++i; i == end(*o); i = begin(*o)) {
        if (++o == end(p->r)) {
          i = {};
          return;
        }
      }
    }
  };

  R r;

  iter b() const { return {{}, this, begin(r), begin(r) == end(r) ? iter_t<IR>() : begin(*begin(r))}; }
  iter e() const { return {{}, this, end(r), {}}; }

 public:
  explicit joined(R&& r) : r(forward<R>(r)) {}
VIEW_END()

TC(R) joined(R&&) -> joined<R>;

TC(R)
VIEW(reversed, R)
  R r;

  auto b() const { return make_reverse_iterator(end(r)); }
  auto e() const { return make_reverse_iterator(begin(r)); }

 public:
  explicit reversed(R&& r) : r(forward<R>(r)) {}
VIEW_END(sz(r))

TC(R) reversed(R&&) -> reversed<R>;
TC(R) reversed(reversed<R>&) -> reversed<reversed<R>&>;
TC(R) reversed(reversed<R> const&) -> reversed<reversed<R> const&>;
TC(R) reversed(reversed<R>&&) -> reversed<reversed<R>>;

TC(R)
VIEW(sliced, R)
  static_assert(is_convertible_v<range_cat<R>, FIT>);

  R r;
  Z start;
  Z stop;

  auto b() const { return next(begin(r), start); }
  auto e() const { return next(begin(r), stop); }

 public:
  explicit sliced(R&& r, Z start, Z stop) : r(forward<R>(r)) {
    Z n = sz(this->r);
    if (start < 0) { start += n; }
    if (stop < 0) { stop += n; }
    this->start = clamp<Z>(start, 0, n);
    this->stop = clamp(stop, this->start, n);
  }
VIEW_END(stop - start)

TC(R) sliced(R&&, Z, Z) -> sliced<R>;

TC(R)
VIEW(strided, R)
  struct iter : iter_base<iter, range_cat<R>, range_ref<R>> {
    strided const* p;
    iter_t<R> i;
    range_ref<R> deref() const { return *i; }
    bool equal(iter const& x) const { return i == x.i; }
    void inc() & {
      if constexpr (is_convertible_v<range_cat<R>, RAIT>) {
        i += min(p->s, Z(end(p->r) - i));
      } else {
        for (Z _ = p->s; _-- && i != end(p->r);) { ++i; }
      }
    }
    void dec() & {
      if (i == end(p->r)) {
        Z n = sz(p->r);
        std::advance(i, (n - 1) / p->s * p->s - n);
      } else {
        std::advance(i, -p->s);
      }
    }
    void advance(Z n) & {
      if (n < 0) {
        dec();
        ++n;
      }
      i += min(p->s * n, Z(end(p->r) - i));
    }
    Z dist_to(iter const& x) const {
      Z d = Z(x.i - i);
      return d < 0 ? div_floor(d, p->s) : div_ceil(d, p->s);
    }
  };

  R r;
  Z s;

  iter b() const { return {{}, this, begin(r)}; }
  iter e() const { return {{}, this, end(r)}; }

 public:
  explicit strided(R&& r, Z s) : r(forward<R>(r)), s(max<Z>(s, 1)) { assert(1 <= s); }
VIEW_END(div_ceil(sz(r), s))

TC(R) strided(R&&, Z) -> strided<R>;

TC(R, class T, class Op)
VIEW(scanned, R, T, Op)
  static_assert(is_convertible_v<range_cat<R>, FIT>);

  struct iter : iter_base<iter, common_type_t<range_cat<R>, FIT>, T> {
    scanned const* p;
    T v;
    iter_t<R> i;
    T deref() const { return v; }
    bool equal(iter const& x) const { return i == x.i && p == x.p; }
    void inc() & {
      if (i == end(p->r)) {
        p = nullptr;
      } else {
        v = invoke(p->op, move(v), *i);
        ++i;
      }
    }
  };

  R r;
  T init;
  [[no_unique_address]] Op op;

  iter b() const { return {{}, this, init, begin(r)}; }
  iter e() const { return {{}, nullptr, {}, end(r)}; }

 public:
  explicit scanned(R&& r, T init, Op op) : r(forward<R>(r)), init(move(init)), op(move(op)) {}
VIEW_END(sz(r) + 1)

TC(R, class T, class Op) scanned(R&&, T, Op) -> scanned<R, T, Op>;

TC(R)
VIEW(sampled, R)
  struct iter : iter_base<iter, common_type_t<range_cat<R>, IIT>, range_ref<R>> {
    iter_t<R> i;
    Z rest;
    Z n;
    range_ref<R> deref() const { return *i; }
    bool equal(iter const& x) const { return i == x.i; }
    void skip() & {
      while (rest && n <= rand<Z>(0, --rest)) { ++i; }
      --n;
    }
    void inc() & {
      ++i;
      skip();
    }
  };

  R r;
  Z n;

  iter b() const {
    iter ret{{}, begin(r), sz(r), n};
    ret.skip();
    return ret;
  }
  iter e() const { return {{}, end(r), 0, 0}; }

 public:
  explicit sampled(R&& r, Z n) : r(forward<R>(r)), n(clamp<Z>(n, 0, sz(this->r))) { assert(0 <= n); }
VIEW_END(min(n, sz(r)))

TC(R) sampled(R&&, Z) -> sampled<R>;

TC(D) class view_base {
  D const& derived() const { return static_cast<D const&>(*this); }  // namespace r7h

 public:
  auto begin() const { return derived().b(); }
  auto end() const { return derived().e(); }
  bool empty() const { return begin() == end(); }
  explicit operator bool() const { return begin() != end(); }
  Z size() const { return Z(end() - begin()); }
  decltype(auto) front() const { return *begin(); }
  decltype(auto) back() const { return *prev(end()); }
  decltype(auto) operator[](Z n) const { return begin()[n]; }

#define WRAP(SIG, CLS, ...) \
  SIG const& { return CLS(derived() __VA_OPT__(,) __VA_ARGS__); } \
  SIG && { return CLS(static_cast<D&&>(*this) __VA_OPT__(,) __VA_ARGS__); }

  WRAP(TC(F) auto filter(F f), filtered, move(f))
  WRAP(TC(F) auto map(F f), mapped, move(f))
  WRAP(template <int N> auto elements(), mapped, LIFT(get<N>))
  WRAP(auto keys(), mapped, LIFT(get<0>))
  WRAP(auto values(), mapped, LIFT(get<1>))
  WRAP(auto take(Z n), taken, n)
  WRAP(TC(F) auto take_while(F f), taken_while, move(f))
  WRAP(auto drop(Z n), dropped, n)
  WRAP(TC(F) auto drop_while(F f), dropped_while, move(f))
  WRAP(auto join(), joined)
  WRAP(auto rev(), reversed)
  WRAP(auto slice(Z l, Z r), sliced, l, r)
  WRAP(auto stride(Z s), strided, s)
  WRAP(TC(T, class Op = plus<>) auto scan(T init, Op op = {}), scanned, move(init), move(op))
  WRAP(auto sample(Z n), sampled, n)

#undef WRAP

#define WRAP(SIG, FN, ...) \
  SIG const { \
    using Res = decltype(std::FN(begin(), end() __VA_OPT__(,) __VA_ARGS__)); \
    if constexpr (is_void_v<Res>) { \
      std::FN(begin(), end() __VA_OPT__(,) __VA_ARGS__); \
      return derived(); \
    } else { \
      auto res = std::FN(begin(), end() __VA_OPT__(,) __VA_ARGS__); \
      if constexpr (is_same_v<decltype(res), iter_t<D>>) { \
        return Z(distance(begin(), move(res))); \
      } else { \
        return res; \
      } \
    } \
  }

  WRAP(TC(F) bool all_of(F f), all_of, ref(f))
  WRAP(TC(F) bool any_of(F f), any_of, ref(f))
  WRAP(TC(F) Z count(F f), count_if, ref(f))
  WRAP(TC(F) Z find(F f), find_if, ref(f))
  WRAP(TC(F) Z adjacent_find(F f), adjacent_find, ref(f))

  WRAP(TC(F) Z remove(F f), remove_if, ref(f))
  WRAP(D const& reverse(), reverse)
  WRAP(D const& shuffle(), shuffle, mt)
  WRAP(TC(C = equal_to<>) Z unique(C comp = {}), unique, ref(comp))

  WRAP(TC(F) bool is_partitioned(F f), is_partitioned, ref(f))
  WRAP(TC(F) Z partition(F f), partition, ref(f))
  WRAP(TC(F) Z stable_partition(F f), stable_partition, ref(f))
  WRAP(TC(F) Z partition_point(F f), partition_point, ref(f))

  WRAP(TC(C = less<>) bool is_sorted(C comp = {}), is_sorted, ref(comp))
  WRAP(TC(C = less<>) Z is_sorted_until(C comp = {}), is_sorted_until, ref(comp))
  WRAP(TC(C = less<>) D const& sort(C comp = {}), sort, ref(comp))
  WRAP(TC(C = less<>) D const& stable_sort(C comp = {}), stable_sort, ref(comp))

  WRAP(TC(T, class C = less<>) Z lower_bound(T const& val, C comp = {}), lower_bound, val, ref(comp))
  WRAP(TC(T, class C = less<>) Z upper_bound(T const& val, C comp = {}), upper_bound, val, ref(comp))
  WRAP(TC(T) bool binary_search(T const& val), binary_search, val)

  WRAP(Z min_element(), min_element)
  WRAP(Z max_element(), max_element)

  WRAP(bool next_permutation(), next_permutation)
  WRAP(bool prev_permutation(), prev_permutation)

  WRAP(TC(T, class Op = plus<>) T fold(T init, Op op = {}), accumulate, move(init), ref(op))

#undef WRAP

  TC(F) D const& each(F f) const {
    for (auto&& e : derived()) {
      if constexpr (is_invocable_v<F&, decltype(e)>) {
        invoke(f, e);
      } else {
        invoke(f);
      }
    }
    return derived();
  }

  TC(F) auto max_right(F f) const { return *prev(std::partition_point(next(begin()), end(), ref(f))); }
  TC(F) auto min_left(F f) const { return *std::partition_point(begin(), prev(end()), not_fn(ref(f))); }

  TC(Op = plus<>)
  auto fold1(Op op = {}) const { return accumulate(next(begin()), end(), front(), ref(op)); }

  template <TC(...) class C = vector>
  auto to() const {
    return C(begin(), end());
  }

  auto to_vla(bool reverse = false) const {
    vla<decay_t<range_ref<D>>> ret(derived().size());
    if (reverse) {
      copy(begin(), end(), make_reverse_iterator(ret.end()));
    } else {
      copy(begin(), end(), ret.begin());
    }
    return ret;
  }
};

TC(D1, class D2) bool operator==(view_base<D1> const& x, view_base<D2> const& y) {
  return equal(begin(x), end(x), begin(y), end(y));
}

TC(D1, class D2) bool operator<(view_base<D1> const& x, view_base<D2> const& y) {
  return lexicographical_compare(begin(x), end(x), begin(y), end(y));
}

TC(R)
VIEW(all, R)
  R r;

  auto b() const { return begin(r); }
  auto e() const { return end(r); }

 public:
  explicit all(R&& r) : r(forward<R>(r)) {}
VIEW_END(sz(r))

TC(R) all(R&&) -> all<R>;
TC(T) all(initializer_list<T>) -> all<initializer_list<T>>;

TC(I)
VIEW(range, I)
  I first;
  I last;

  I b() const { return first; }
  I e() const { return last; }

 public:
  explicit range(I first, I last) : first(move(first)), last(move(last)) {}
VIEW_END()

TC(T) auto rep(T l, T r) { return range(int_iter(min(l, r)), int_iter(r)); }

TC(T) auto rep(T n) { return rep<T>(0, n); }

TC(T) auto rep1(T l, T r) { return rep(l, r + 1); }

TC(T) auto rep1(T n) { return rep1<T>(1, n); }

TC(G)
VIEW(generation, G)
  using T = decay_t<invoke_result_t<G const&>>;

  struct iter : iter_base<iter, IIT, T> {
    generation const* p;
    T v;
    T deref() const { return v; }
    bool equal(iter const& x) const { return p == x.p; }
    void inc() & { v = invoke(p->gen); }
  };

  [[no_unique_address]] G gen;

  iter b() const { return {{}, this, invoke(gen)}; }
  iter e() const { return {{}, nullptr, {}}; }

 public:
  explicit generation(G gen) : gen(move(gen)) {}
VIEW_END(numeric_limits<Z>::max())

TC(T) auto repeat(T val) {
  return generation([val = move(val)] { return val; });
}

TC(T) auto rand_view(T a, T b) {
  return generation([a, b] { return rand(a, b); });
}

TC(T, class F)
VIEW(iteration, T, F)
  struct iter : iter_base<iter, FIT, T> {
    iteration const* p;
    T v;
    T deref() const { return v; }
    bool equal(iter const& x) const { return p == x.p; }
    void inc() & { v = invoke(p->f, move(v)); }
  };

  T init;
  [[no_unique_address]] F f;

  iter b() const { return {{}, this, init}; }
  iter e() const { return {{}, nullptr, {}}; }

 public:
  explicit iteration(T init, F f) : init(move(init)), f(move(f)) {}
VIEW_END(numeric_limits<Z>::max())

#undef TC
#undef Z
#undef IIT
#undef FIT
#undef BIT
#undef RAIT
#undef VIEW
#undef VIEW_END

}  // namespace r7h

int main() { r7h::rep(MULTI_CASES ? r7h::input() : 1).each(r7h::main); }

#include <atcoder/modint>
#include <atcoder/string>

#endif
yukicoder

結果

テストケース

ソースコード
