#470832 (C++17) No.1036 Make One With GCD 2

提出ソース

結果

問題	No.1036 Make One With GCD 2
ユーザー	rsk0315
提出日時	2020-04-25 19:58:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	711 ms / 2,000 ms
コード長	4,964 bytes
コンパイル時間	1,081 ms
コンパイル使用メモリ	66,920 KB
実行使用メモリ	22,400 KB
最終ジャッジ日時	2024-11-07 18:07:25
合計ジャッジ時間	16,223 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	711 ms 22,400 KB
testcase_01	AC	306 ms 22,400 KB
testcase_02	AC	320 ms 22,272 KB
testcase_03	AC	83 ms 9,984 KB
testcase_04	AC	157 ms 15,488 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	127 ms 11,136 KB
testcase_08	AC	102 ms 9,600 KB
testcase_09	AC	360 ms 21,760 KB
testcase_10	AC	350 ms 20,480 KB
testcase_11	AC	367 ms 22,272 KB
testcase_12	AC	358 ms 20,608 KB
testcase_13	AC	472 ms 21,504 KB
testcase_14	AC	474 ms 21,504 KB
testcase_15	AC	434 ms 20,352 KB
testcase_16	AC	451 ms 20,480 KB
testcase_17	AC	442 ms 20,992 KB
testcase_18	AC	3 ms 5,248 KB
testcase_19	AC	3 ms 5,248 KB
testcase_20	AC	4 ms 5,248 KB
testcase_21	AC	4 ms 5,248 KB
testcase_22	AC	435 ms 20,224 KB
testcase_23	AC	322 ms 15,616 KB
testcase_24	AC	444 ms 20,864 KB
testcase_25	AC	407 ms 19,200 KB
testcase_26	AC	433 ms 19,840 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	3 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	319 ms 22,400 KB
testcase_39	AC	628 ms 22,400 KB
testcase_40	AC	325 ms 15,488 KB
testcase_41	AC	643 ms 22,272 KB
testcase_42	AC	618 ms 22,272 KB
testcase_43	AC	673 ms 22,272 KB
testcase_44	AC	704 ms 22,400 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "test/yc_1036_bisect.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1036"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <vector>

#line 1 "DataStructure/basic_segment_tree.cpp"



/**
 * @brief 単一更新セグメント木
 * @author えびちゃん
 */

#include <cstddef>
#line 12 "DataStructure/basic_segment_tree.cpp"

template <typename Monoid>
class basic_segment_tree {
public:
  using value_type = Monoid;
  using size_type = size_t;

private:
  std::vector<value_type> M_c;
  size_type M_n;

  std::vector<size_type> M_covering_segments(size_type l, size_type r) const {
    std::vector<size_type> left, right;
    l += M_n;
    r += M_n;
    while (l < r) {
      if (l & 1) left.push_back(l++);
      if (r & 1) right.push_back(--r);
      l >>= 1;
      r >>= 1;
    }
    left.insert(left.end(), right.rbegin(), right.rend());
    return left;
  }

public:
  basic_segment_tree() = default;

  explicit basic_segment_tree(size_type n): M_c(n+n), M_n(n) {}
  explicit basic_segment_tree(size_type n, value_type const& x):
    M_c(n+n, x), M_n(n)
  {
    for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  template <typename InputIt>
  basic_segment_tree(InputIt first, InputIt last) {
    std::vector<value_type> tmp(first, last);
    M_n = tmp.size();
    M_c.resize(M_n);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  void assign(size_type n, value_type const& x) {
    M_c.assign(n+n, x);
    M_n = n;
    for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    std::vector<value_type> tmp(first, last);
    M_n = tmp.size();
    M_c.resize(M_n);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  void set(size_type i, value_type const& x) {
    i += M_n;
    M_c[i] = x;
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
    }
  }

  void set(size_type i, value_type&& x) {
    i += M_n;
    M_c[i] = std::move(x);
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
    }
  }

  value_type const& operator [](size_type i) const { return M_c[i + M_n]; }

  value_type fold(size_type l, size_type r) const {
    value_type resl{}, resr{};
    l += M_n;
    r += M_n;
    while (l < r) {
      if (l & 1) resl += M_c[l++];
      if (r & 1) resr = M_c[--r] + std::move(resr);
      l >>= 1;
      r >>= 1;
    }
    return resl += resr;
  }

  template <typename Predicate>
  size_type foldl_bisect(size_type l, Predicate pred) const {
    if (l == M_n) return l;
    value_type x{};
    size_type v = M_n+M_n;
    std::vector<size_type> cs = M_covering_segments(l, M_n);

    // search the subroot
    for (auto s: cs) {
      if (!pred(x + M_c[s])) {
        v = s;
        break;
      }
      x += M_c[s];
    }

    // search the leaf
    while (v < M_n) {
      v <<= 1;
      if (pred(x + M_c[v])) {
        x += M_c[v];
        v |= 1;
      }
    }

    return v - M_n;
  }

  template <typename Predicate>
  size_type foldr_bisect(size_type r, Predicate pred) const {
    if (r == 0) return r;
    value_type x{};
    size_type v = M_n+M_n;
    std::vector<size_type> cs = M_covering_segments(0, r);
    std::reverse(cs.begin(), cs.end());

    // search the subroot
    for (auto s: cs) {
      if (!pred(M_c[s] + x)) {
        v = s;
        break;
      }
      x = M_c[s] + std::move(x);
    }
    if (v == M_n+M_n) return -1;  // always true

    // search the leaf
    while (v < M_n) {
      v <<= 1;
      if (pred(M_c[v|1] + x)) {
        x = M_c[v|1] + std::move(x);
      } else {
        v |= 1;
      }
    }

    return v - M_n;
  }
};


#line 10 "test/yc_1036_bisect.test.cpp"

template <typename Tp>
class gcd_monoid {
public:
  using value_type = Tp;

private:
  value_type M_x = 0;

public:
  gcd_monoid() = default;  // identity

  gcd_monoid(value_type const& x): M_x(x) {}

  gcd_monoid& operator +=(gcd_monoid const& that) {
    M_x = std::gcd(M_x, that.M_x);
    return *this;
  }
  friend bool operator ==(gcd_monoid const& lhs, gcd_monoid const& rhs) {
    return lhs.M_x == rhs.M_x;
  }

  friend gcd_monoid operator +(gcd_monoid lhs, gcd_monoid const& rhs) { return lhs += rhs; }
  friend bool operator !=(gcd_monoid const& lhs, gcd_monoid const& rhs) {
    return !(lhs == rhs);
  }

  value_type const& get() const { return M_x; }
};

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<intmax_t> a(n);
  for (auto& ai: a) scanf("%jd", &ai);

  basic_segment_tree<gcd_monoid<intmax_t>> st(a.begin(), a.end());
  auto pred = [](auto x) { return x.get() > 1; };

  intmax_t res = 0;
  for (size_t i = 0; i < n; ++i) {
    size_t j = st.foldl_bisect(i, pred);
    if (j <= n) res += n-j;
  }

  printf("%jd\n", res);
}