結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー |
|
提出日時 | 2024-12-13 18:39:32 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 646 ms / 5,000 ms |
コード長 | 9,325 bytes |
コンパイル時間 | 4,505 ms |
コンパイル使用メモリ | 285,348 KB |
実行使用メモリ | 26,592 KB |
最終ジャッジ日時 | 2024-12-13 18:39:53 |
合計ジャッジ時間 | 18,515 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 4 ms
5,248 KB |
testcase_02 | AC | 4 ms
5,248 KB |
testcase_03 | AC | 4 ms
5,248 KB |
testcase_04 | AC | 4 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 4 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 5 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 568 ms
21,376 KB |
testcase_12 | AC | 584 ms
22,400 KB |
testcase_13 | AC | 402 ms
20,332 KB |
testcase_14 | AC | 540 ms
25,240 KB |
testcase_15 | AC | 616 ms
25,344 KB |
testcase_16 | AC | 625 ms
25,652 KB |
testcase_17 | AC | 539 ms
26,496 KB |
testcase_18 | AC | 532 ms
26,552 KB |
testcase_19 | AC | 427 ms
25,312 KB |
testcase_20 | AC | 448 ms
26,592 KB |
testcase_21 | AC | 424 ms
24,632 KB |
testcase_22 | AC | 411 ms
25,984 KB |
testcase_23 | AC | 456 ms
24,832 KB |
testcase_24 | AC | 365 ms
25,272 KB |
testcase_25 | AC | 381 ms
26,432 KB |
testcase_26 | AC | 420 ms
24,576 KB |
testcase_27 | AC | 377 ms
25,880 KB |
testcase_28 | AC | 392 ms
24,960 KB |
testcase_29 | AC | 587 ms
25,360 KB |
testcase_30 | AC | 597 ms
25,344 KB |
testcase_31 | AC | 646 ms
25,728 KB |
testcase_32 | AC | 276 ms
26,496 KB |
testcase_33 | AC | 379 ms
25,252 KB |
testcase_34 | AC | 396 ms
25,600 KB |
testcase_35 | AC | 423 ms
25,344 KB |
testcase_36 | AC | 392 ms
26,112 KB |
testcase_37 | AC | 386 ms
25,728 KB |
ソースコード
#line 1 "test/yukicoder/880.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/880" #line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; // https://xn--kst.jp/blog/2019/08/29/cpp-comp/ // debug methods // usage: debug(x,y); // vector 出力できるように修正 template <typename T> ostream& debug_print(ostream& os, const vector<T>& v) { os << "["; for (size_t i = 0; i < v.size(); ++i) { os << v[i]; if (i < v.size() - 1) os << ", "; } os << "]"; return os; } template <typename T> ostream& debug_print(ostream& os, const T& var) { os << var; return os; } #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) { cout << #x1 << ": "; debug_print(cout, x1) << endl; } #define debug_2(x1, x2) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << endl; } #define debug_3(x1, x2, x3) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << endl; } #define debug_4(x1, x2, x3, x4) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << endl; } #define debug_5(x1, x2, x3, x4, x5) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << ", " << #x5 << ": "; debug_print(cout, x5) << endl; } #ifdef LOCAL #define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~))(__VA_ARGS__) #else #define debug(...) #endif using ll = long long; using vl = vector<ll>; using Graph = vector<vector<ll>>; using P = pair<ll, ll>; #define all(v) v.begin(), v.end() template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } #define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i) // https://trap.jp/post/1224/ template <class... T> constexpr auto min(T... a) { return min(initializer_list<common_type_t<T...>>{a...}); } template <class... T> constexpr auto max(T... a) { return max(initializer_list<common_type_t<T...>>{a...}); } template <class... T> void input(T &...a) { (cin >> ... >> a); } template <class T> void input(vector<T> &a) { for(T &x : a) cin >> x; } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } void print(const string &s) { cout << s << '\n'; } template <class Container, typename = void> struct is_container : std::false_type {}; template <class Container> struct is_container<Container, std::void_t<decltype(std::declval<Container>().begin()), decltype(std::declval<Container>().end())>> : std::true_type {}; template <class Container> typename enable_if<is_container<Container>::value>::type print(const Container& x) { if (!x.empty()) { auto it = x.begin(); for (; it != prev(x.end()); ++it) { cout << *it << " "; } cout << *it << "\n"; // 最後の要素を出力して改行 } } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1(a) for(ll i = 0; i < a; i++) #define REP2(i, a) for(ll i = 0; i < a; i++) #define REP3(i, a, b) for(ll i = a; i < b; i++) #define REP4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; #line 2 "data_structure/segtree-beats.hpp" // https://rsm9.hatenablog.com/entry/2021/02/01/220408 template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> // composition(f,g)(x) = f∘g(x) = f(g(x)) // aclと同じ、maspyさん記事と逆 struct segtree_beats { vector<S> v; vector<F> vf; ll n; segtree_beats(ll n) : n(n), v(vector<S>(2 * n, e())), vf(vector<F>(2 * n, id())) {}; segtree_beats(vector<S> v_) : n(v_.size()) { vf = vector<F>(2 * n, id()); v = vector<S>(2 * n, e()); rep(i, n) { v[i + n] = v_[i]; } for(ll i = n - 1; i > 0; i--) { v[i] = op(v[i << 1], v[i << 1 | 1]); } } void apply(ll l, ll r, F f) { l += n; r += n; ll l0 = l / (l & -l); ll r0 = r / (r & -r) - 1; propagate_above(l0); propagate_above(r0); while(l < r) { if(l & 1) { apply_at(l, f); l++; } if(r & 1) { r--; apply_at(r, f); } l >>= 1; r >>= 1; } recul_above(l0); recul_above(r0); } S get(ll x) { x += n; ll maxi = bit_length(x) - 1; for(ll i = maxi; i > 0; i--) { propagate_at(x >> i); } return v[x]; } void set(ll x, S s) { x += n; propagate_above(x); v[x] = s; recul_above(x); } S prod(ll l, ll r) { l += n; r += n; ll l0 = l / (l & -l); ll r0 = r / (r & -r) - 1; propagate_above(l0); propagate_above(r0); S sl = e(), sr = e(); while(l < r) { if(l & 1) { sl = op(sl, v[l]); l++; } if(r & 1) { r--; sr = op(v[r], sr); } l >>= 1; r >>= 1; } return op(sl, sr); } private: void apply_at(ll x, F f) { v[x] = mapping(f, v[x]); if(x < n) { vf[x] = composition(f, vf[x]); // Added for Segment Tree Beats implementation. if(v[x].fail) { propagate_at(x); v[x] = op(v[x << 1], v[x << 1 | 1]); } } } void propagate_at(ll x) { apply_at(x << 1, vf[x]); apply_at(x << 1 | 1, vf[x]); vf[x] = id(); } ll bit_length(unsigned long long x) { return 64 - countl_zero(x); } void propagate_above(ll x) { ll maxi = bit_length(x) - 1; for(ll i = maxi; i > 0; i--) { propagate_at(x >> i); } return; } void recul_above(ll x) { while(x > 1) { x >>= 1; v[x] = op(v[x << 1], v[x << 1 | 1]); } } }; #line 4 "test/yukicoder/880.test.cpp" struct S { ll mini, maxi, lcm, num, sum; bool fail; S(ll a, ll num_ = 1) : mini(a), maxi(a), lcm(a), num(num_), sum(a * num_), fail(false) {}; S() = default; }; S e() { return S(0, 0); } S op(S a, S b) { S res = e(); res.mini = min(a.mini, b.mini); res.maxi = max(a.maxi, b.maxi); res.lcm = lcm(a.lcm, b.lcm); if(a.lcm == inf or b.lcm == inf or __int128_t(a.lcm) * b.lcm / (1 + gcd(a.lcm, b.lcm)) >= inf) res.lcm = inf; res.num = a.num + b.num; res.sum = a.sum + b.sum; res.fail = a.fail or b.fail; return res; } struct F { // gcdやってassign bool gcd_q, assing_q; ll g, x; }; S mapping(F f, S s) { if(s.fail) { return s; } if(f.assing_q) { return S(f.x, s.num); } if(f.gcd_q) { if(s.mini == s.maxi) { ll val = gcd(s.mini, f.g); return S(val, s.num); } if(f.g % s.lcm) s.fail = true; } return s; } F id() { return F(false, false, 0, 0); } F composition(F f1, F f2) { if(f1.assing_q or (!f2.assing_q and !f2.gcd_q)) { return f1; } if(!f1.gcd_q) { return f2; } if(f2.assing_q) { return F(false, true, 0, gcd(f1.g, f2.x)); } f1.g = gcd(f1.g, f2.g); return f1; } void solve() { LL(n, q); vector<S> a(n); rep(i, n) { LL(ai); a[i] = S(ai); } segtree_beats<S, op, e, F, mapping, composition, id> seg(a); while(q--) { LL(flag); LL(l, r); l--; if(flag == 1) { LL(x); seg.apply(l, r, F(false, true, 0, x)); } else if(flag == 2) { LL(x); seg.apply(l, r, F(true, false, x, 0)); } else if(flag == 3) { print(seg.prod(l, r).maxi); } else { print(seg.prod(l, r).sum); } } } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); ll t = 1; rep(_, t) solve(); }