結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | rsk0315 |
提出日時 | 2020-04-25 20:03:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,052 bytes |
コンパイル時間 | 815 ms |
コンパイル使用メモリ | 69,044 KB |
実行使用メモリ | 28,416 KB |
最終ジャッジ日時 | 2024-04-25 07:56:20 |
合計ジャッジ時間 | 18,240 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,343 ms
28,416 KB |
testcase_01 | AC | 262 ms
22,912 KB |
testcase_02 | AC | 377 ms
22,784 KB |
testcase_03 | AC | 79 ms
10,368 KB |
testcase_04 | AC | 151 ms
16,000 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 113 ms
11,648 KB |
testcase_08 | AC | 90 ms
10,112 KB |
testcase_09 | AC | 400 ms
22,400 KB |
testcase_10 | AC | 391 ms
21,120 KB |
testcase_11 | AC | 406 ms
22,784 KB |
testcase_12 | AC | 401 ms
21,248 KB |
testcase_13 | AC | 536 ms
22,016 KB |
testcase_14 | AC | 548 ms
22,144 KB |
testcase_15 | AC | 505 ms
20,992 KB |
testcase_16 | AC | 529 ms
21,120 KB |
testcase_17 | AC | 578 ms
21,632 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 3 ms
5,376 KB |
testcase_20 | AC | 4 ms
5,376 KB |
testcase_21 | AC | 3 ms
5,376 KB |
testcase_22 | AC | 505 ms
20,736 KB |
testcase_23 | AC | 372 ms
16,128 KB |
testcase_24 | AC | 521 ms
21,632 KB |
testcase_25 | AC | 467 ms
19,840 KB |
testcase_26 | AC | 498 ms
20,480 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 1 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 1 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 1 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 372 ms
22,912 KB |
testcase_39 | TLE | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
#line 1 "test/yc_1036_bisect.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1036" #include <cstdint> #include <cstdio> #include <algorithm> #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 9 "test/yc_1036_bisect.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); 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); }