結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | rsk0315 |
提出日時 | 2020-04-25 20:40:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,425 bytes |
コンパイル時間 | 656 ms |
コンパイル使用メモリ | 67,116 KB |
実行使用メモリ | 77,524 KB |
最終ジャッジ日時 | 2024-04-25 08:54:18 |
合計ジャッジ時間 | 24,705 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 439 ms
77,524 KB |
testcase_01 | AC | 418 ms
77,392 KB |
testcase_02 | AC | 213 ms
77,388 KB |
testcase_03 | AC | 134 ms
28,688 KB |
testcase_04 | AC | 241 ms
50,072 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 165 ms
32,968 KB |
testcase_08 | AC | 132 ms
27,112 KB |
testcase_09 | AC | 531 ms
75,676 KB |
testcase_10 | AC | 485 ms
70,412 KB |
testcase_11 | AC | 542 ms
77,108 KB |
testcase_12 | AC | 504 ms
70,984 KB |
testcase_13 | AC | 667 ms
73,692 KB |
testcase_14 | AC | 669 ms
74,680 KB |
testcase_15 | AC | 613 ms
69,848 KB |
testcase_16 | AC | 618 ms
70,420 KB |
testcase_17 | AC | 635 ms
72,560 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 4 ms
5,376 KB |
testcase_21 | AC | 4 ms
5,376 KB |
testcase_22 | AC | 603 ms
68,864 KB |
testcase_23 | AC | 436 ms
50,508 KB |
testcase_24 | AC | 626 ms
71,840 KB |
testcase_25 | AC | 572 ms
65,300 KB |
testcase_26 | AC | 620 ms
67,848 KB |
testcase_27 | AC | 1 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 | 2 ms
5,376 KB |
testcase_34 | AC | 1 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 214 ms
77,388 KB |
testcase_39 | AC | 451 ms
77,388 KB |
testcase_40 | AC | 445 ms
50,508 KB |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | TLE | - |
ソースコード
#line 1 "test/yc_1036_sparse_table.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1036" #include <cstdint> #include <cstdio> #include <algorithm> #include <vector> #line 1 "DataStructure/sparse_table.cpp" /** * @brief sparse table * @author えびちゃん */ #include <cstddef> #line 11 "DataStructure/sparse_table.cpp" #line 1 "utility/literals.cpp" /** * @brief ユーザ定義リテラル * @author えびちゃん */ #line 11 "utility/literals.cpp" constexpr intmax_t operator ""_jd(unsigned long long n) { return n; } constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; } constexpr size_t operator ""_zu(unsigned long long n) { return n; } constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; } #line 1 "integer/bit.cpp" /** * @brief ビット演算 * @author えびちゃん */ // XXX integral promotion 関連の注意をあまりしていません #include <climits> #include <type_traits> template <typename Tp> constexpr auto countl_zero(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { using value_type = typename std::make_unsigned<Tp>::type; int bits = (sizeof(value_type) * CHAR_BIT); if (n == 0) return bits; int res = 0; for (int i = bits / 2; i > 0; i /= 2) { value_type mask = ((static_cast<value_type>(1) << i) - 1) << i; if (n & mask) n >>= i; else res += i; } return res; } template <typename Tp> constexpr auto countl_one(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { using value_type = typename std::make_unsigned<Tp>::type; return countl_zero(static_cast<value_type>(~n)); } template <typename Tp> constexpr auto countr_zero(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { using value_type = typename std::make_unsigned<Tp>::type; int bits = (sizeof(value_type) * CHAR_BIT); if (n == 0) return bits; int res = 0; for (int i = bits / 2; i > 0; i /= 2) { value_type mask = ((static_cast<value_type>(1) << i) - 1); if (!(n & mask)) res += i, n >>= i; } return res; } template <typename Tp> constexpr auto countr_one(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { using value_type = typename std::make_unsigned<Tp>::type; return countr_zero(static_cast<value_type>(~n)); } constexpr unsigned long long half_mask[] = { 0x5555555555555555uLL, 0x3333333333333333uLL, 0x0F0F0F0F0F0F0F0FuLL, 0x00FF00FF00FF00FFuLL, 0x0000FFFF0000FFFFuLL, 0x00000000FFFFFFFFuLL }; template <typename Tp> constexpr auto popcount(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { int bits = static_cast<int>((sizeof n) * CHAR_BIT); for (int i = 0, j = 1; j < bits; ++i, j *= 2) { if (j <= 8) n = (n & half_mask[i]) + ((n >> j) & half_mask[i]); else n += n >> j; } return n & 0xFF; } template <typename Tp> constexpr auto parity(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type { return popcount(n) & 1; } template <typename Tp> int clz(Tp n) { return countl_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); } template <typename Tp> int ctz(Tp n) { return countr_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); } template <typename Tp> int ilog2(Tp n) { return (CHAR_BIT * sizeof(Tp) - 1) - clz(static_cast<typename std::make_unsigned<Tp>::type>(n)); } template <typename Tp> bool is_pow2(Tp n) { return (n > 0) && ((n & (n-1)) == 0); } template <typename Tp> Tp floor2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(1) << ilog2(n); } template <typename Tp> Tp ceil2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(2) << ilog2(n); } template <typename Tp> constexpr auto reverse(Tp n) -> typename std::enable_if<std::is_unsigned<Tp>::value, Tp>::type { int bits = static_cast<int>((sizeof n) * CHAR_BIT); for (int i = 0, j = 1; j < bits; ++i, j *= 2) { n = ((n & half_mask[i]) << j) | ((n >> j) & half_mask[i]); } return n; } #line 14 "DataStructure/sparse_table.cpp" template <typename Band> class sparse_table { public: using size_type = size_t; using value_type = Band; private: std::vector<std::vector<value_type>> M_c; public: sparse_table() = default; template <typename InputIt> sparse_table(InputIt first, InputIt last) { assign(first, last); } template <typename InputIt> sparse_table(std::initializer_list<value_type> il) { assign(il.begin(), il.end()); } template <typename InputIt> void assign(InputIt first, InputIt last) { M_c.assign(1, std::vector<value_type>(first, last)); size_type n = M_c[0].size(); for (size_type i = 1, ii = 1; M_c.back().size() > ii; (++i, ii <<= 1)) { M_c.emplace_back(); M_c.back().reserve(n - ii); for (size_type j = ii; j < M_c[i-1].size(); ++j) M_c[i].push_back(M_c[i-1][j] + M_c[i-1][j-ii]); } } void assign(std::initializer_list<value_type> il) { assign(il.begin(), il.end()); } value_type fold(size_type l, size_type r) const { size_type e = ilog2(r-l); r -= (1_zu << e) - 1; return M_c[e][l] + M_c[e][r-1]; } }; #line 9 "test/yc_1036_sparse_table.test.cpp" template <typename Tp> class gcd_monoid { public: using value_type = Tp; private: value_type M_x = 0; static value_type S_gcd(value_type x, value_type y) { while (y) std::swap(x %= y, y); return x; } public: gcd_monoid() = default; // identity gcd_monoid(value_type const& x): M_x(x) {} gcd_monoid& operator +=(gcd_monoid const& that) { M_x = S_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); sparse_table<gcd_monoid<intmax_t>> st(a.begin(), a.end()); intmax_t res = 0; for (size_t i = 0; i < n; ++i) { if (st.fold(i, n).get() > 1) break; size_t lb = i, ub = n; while (ub-lb > 1) { size_t mid = (lb+ub) / 2; ((st.fold(i, mid).get() > 1)? lb: ub) = mid; } res += n-lb; } printf("%jd\n", res); }