Submit Info #54154

Problem Lang User Status Time Memory
Range Affine Range Sum cpp-acl nor AC 424 ms 35.21 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
max_random_00 AC 405 ms 35.21 MiB
max_random_01 AC 397 ms 35.20 MiB
max_random_02 AC 424 ms 35.21 MiB
random_00 AC 322 ms 28.08 MiB
random_01 AC 341 ms 31.09 MiB
random_02 AC 177 ms 13.34 MiB
small_00 AC 1 ms 0.71 MiB
small_01 AC 1 ms 0.72 MiB
small_02 AC 1 ms 0.72 MiB
small_03 AC 1 ms 0.71 MiB
small_04 AC 1 ms 0.71 MiB
small_05 AC 1 ms 0.71 MiB
small_06 AC 1 ms 0.71 MiB
small_07 AC 1 ms 0.71 MiB
small_08 AC 1 ms 0.71 MiB
small_09 AC 1 ms 0.71 MiB
small_random_00 AC 1 ms 0.71 MiB
small_random_01 AC 1 ms 0.72 MiB

/* source: https://judge.yosupo.jp/submission/49266 just to check if there is some decay in the judge's speed */ #line 1 "main.cpp" #line 2 "lib/prelude.hpp" #ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #endif #include <bits/stdc++.h> using std::move; using std::pair; using std::tuple; template <class T> using vec = std::vector<T>; using uint = unsigned; using ll = long long; using ull = unsigned long long; template <class T, class U> bool chmin(T& var, U x) { return var > x ? var = x, true : false; } template <class T, class U> bool chmax(T& var, U x) { return var < x ? var = x, true : false; } template <class T> T divceil(T a, T b) { return (a - 1) / b + 1; } template <class T> T abs_diff(T a, T b) { return a > b ? a - b : b - a; } template <class T> std::enable_if_t<std::is_unsigned_v<T>, T> ssub(T a, T b) { T c = a - b; return c > a ? 0 : c; } #line 3 "lib/alg.hpp" template <class Unit, class Op> struct monoid : private Unit, private Op { using type = decltype(std::declval<Unit>()()); monoid(Unit unit, Op op) : Unit(unit), Op(op) {} type unit() const { return static_cast<const Unit&>(*this)(); } type op(type a, type b) const { return static_cast<const Op&>(*this)(a, b); } }; template <class Unit, class Op, class Inv> struct group : public monoid<Unit, Op>, private Inv { using type = typename monoid<Unit, Op>::type; group(Unit unit, Op op, Inv inv) : monoid<Unit, Op>(unit, op), Inv(inv) {} type inv(type a) const { return static_cast<const Inv&>(*this)(a); } }; template <class T> struct addition { using type = T; type unit() const { return 0; } type op(type a, type b) const { return a + b; } type inv(type a) const { return -a; } }; template <class T> struct maximum { using type = T; type unit() const { return std::numeric_limits<T>::min(); } type op(type a, type b) const { return a > b ? a : b; } }; template <class T> struct minimum { using type = T; type unit() const { return std::numeric_limits<T>::max(); } type op(type a, type b) const { return a > b ? b : a; } }; #line 3 "lib/bit/ctz.hpp" template <class T> uint ctz(T a) { if (!a) return sizeof(T) * 8; if constexpr (sizeof(T) <= sizeof(uint)) { return (uint)(__builtin_ctz((uint)a)); } else if constexpr (sizeof(T) <= sizeof(ull)) { return (uint)(__builtin_ctzll((ull)a)); } else { static_assert(sizeof(T) == sizeof(ull) * 2); uint l = ctz((ull)a); return l != sizeof(ull) * 8 ? l : l + ctz((ull)(a >> sizeof(ull) * 8)); } } #line 3 "lib/bit/clz.hpp" template <class T> uint clz(T a) { if (!a) return sizeof(T) * 8; if constexpr (sizeof(T) <= sizeof(uint)) { return (uint)(__builtin_clz((uint)a)); } else if constexpr (sizeof(T) <= sizeof(ull)) { return (uint)(__builtin_clzll((ull)a)); } else { static_assert(sizeof(T) == sizeof(ull) * 2); uint l = clz((ull)(a >> sizeof(ull) * 8)); return l != sizeof(ull) * 8 ? l : l + clz((ull)a); } } #line 4 "lib/bit/ilog2.hpp" template <class T> uint ilog2(T a) { #ifdef LOCAL assert(a != 0); #endif return (uint)(sizeof(T) * 8 - 1) - clz(a); } template <class T> uint ilog2_ceil(T a) { return a == 0 || a == 1 ? 1 : ilog2(a - 1); } #line 6 "lib/ds/lazy_segtree.hpp" template <class M, class A, class Act> class lazy_segment_tree : private M, private A, private Act { public: using value_type = typename M::type; using actor_type = typename A::type; lazy_segment_tree(const std::vector<value_type>& data, M m, A a, Act f) : M(m), A(a), Act(f), data_(data.size() * 2), lazy_(data.size(), static_cast<const A*>(this)->unit()) { std::copy(data.cbegin(), data.cend(), data_.begin() + size()); for (size_t i = size(); --i;) data_[i] = static_cast<const M*>(this)->op(data_[i << 1], data_[i << 1 | 1]); } lazy_segment_tree(size_t n, M m, A a, Act f) : M(m), A(a), Act(f), data_(n * 2, static_cast<const M*>(this)->unit()), lazy_(n, static_cast<const A*>(this)->unit()) {} size_t size() const { return data_.size() / 2; } value_type ask(size_t l, size_t r) { flush(trunc(l + size())); flush(trunc(r + size()) - 1); value_type accl = static_cast<const M*>(this)->unit(), accr = static_cast<const M*>(this)->unit(); for (l += size(), r += size(); l < r; l >>= 1, r >>= 1) { if (l & 1) accl = static_cast<const M*>(this)->op(accl, data_[l++]); if (r & 1) accr = static_cast<const M*>(this)->op(data_[--r], accr); } return static_cast<const M*>(this)->op(accl, accr); } void act(size_t l, size_t r, actor_type a) { if (a == static_cast<const A*>(this)->unit()) return; flush(trunc(l + size())); flush(trunc(r + size()) - 1); for (size_t l2 = l + size(), r2 = r + size(); l2 < r2; l2 >>= 1, r2 >>= 1) { if (l2 & 1) apply(l2++, a); if (r2 & 1) apply(--r2, a); } build(trunc(l + size())); build(trunc(r + size()) - 1); } private: std::vector<value_type> data_; std::vector<actor_type> lazy_; static size_t trunc(size_t a) { return a >> ctz(a); } void apply(size_t i, actor_type a) { data_[i] = static_cast<const Act&>(*this)(data_[i], a); if (i < size()) lazy_[i] = static_cast<const A*>(this)->op(lazy_[i], a); } void push(size_t i) { if (lazy_[i] != static_cast<const A*>(this)->unit()) { apply(i << 1, lazy_[i]); apply(i << 1 | 1, lazy_[i]); lazy_[i] = static_cast<const A*>(this)->unit(); } } void upd(size_t i) { data_[i] = static_cast<const M*>(this)->op(data_[i << 1], data_[i << 1 | 1]); } void flush(size_t i) { if (i) for (uint s = ilog2(i); s > 0; s--) push(i >> s); } void build(size_t i) { for (; i >>= 1;) upd(i); } }; #line 3 "lib/io.hpp" #ifndef BUF_SIZE #define BUF_SIZE (1 << 25) #endif namespace s16_io { char in[BUF_SIZE], out[BUF_SIZE], *s, *t; void read(char &x) { while (*s <= ' ') s++; x = *s++; } template <class T> std::enable_if_t<std::is_integral_v<T>, void> read(T &x) { while (*s <= ' ') ++s; bool neg = false; if constexpr (std::is_signed_v<T>) neg = *s == '-' ? ++s, true : false; x = 0; while (*s > ' ') x = x * 10 + (*s++ & 0x0F); if (neg) x = -x; } template <class T> auto read(T& v) -> decltype(v.val(), void()) { uint x; read(x); v = x; } template <class T> void read(std::vector<T> &v) { for (auto &e : v) read(e); } void read(std::string &str) { while (*s <= ' ') s++; char *s0 = s; while (*s > ' ') s++; str.clear(), str.append(s0, s); } template <class T, class... Rest> void read(T &x, Rest &...rest) { read(x); read(rest...); } void write(char x) { *t++ = x; } template <class T> std::enable_if_t<std::is_integral_v<T>, void> write(T x) { if (!x) { *t++ = '0'; return; } if (x < 0) *t++ = '-', x = -x; static char tmp[20], *p; p = tmp + 20; while (x) *--p = '0' + static_cast<char>(x % 10), x /= 10; size_t len = tmp + 20 - p; std::memcpy(t, p, len), t += len; } template <class T> auto write(T x) -> decltype(x.val(), void()) { write(x.val()); } void write(const std::string &str) { std::memcpy(t, str.c_str(), str.size()), t += str.size(); } void write(const char *str) { size_t len = std::strlen(str); std::memcpy(t, str, len), t += len; } class IO { public: IO() { s = in, t = out, in[std::fread(in, 1, sizeof(in), stdin)] = 0; } ~IO() { std::fwrite(out, 1, t - out, stdout); } } io_dummy; } // namespace s16_io using s16_io::read; using s16_io::write; template <class T> void prtln(T x) { write(x); write('\n'); } template <class T, class... Rest> void prtln(T x, Rest... rest) { write(x), write(' '), prtln(rest...); } template <class T> void prtln(const vec<T> &v, char sep = ' ') { for (size_t i = 0; i < v.size(); i++) write(v[i]), write(i != v.size() - 1 ? sep : '\n'); } void YesNo(bool b) { prtln(b ? "Yes" : "No"); } void YESNO(bool b) { prtln(b ? "YES" : "NO"); } #line 5 "main.cpp" #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { size_t n, q; read(n, q); vec<pair<mint, mint>> a(n); for (auto& [e, k] : a) read(e), k = mint(1); lazy_segment_tree ds(a, monoid([]{ return pair(mint(0), mint(0)); }, [](auto p, auto q) { auto [x, y] = p; auto [z, w] = q; return pair(x + z, y + w); }), monoid([]{ return pair(mint(1), mint(0)); }, [](auto p, auto q) { auto [a, b] = p; auto [c, d] = q; return pair(a * c, b * c + d); }), [](auto p, auto q) { auto [x, y] = p; auto [a, b] = q; return pair(a * x + b * y, y); } ); while (q--) { char t; size_t l, r; read(t, l, r); if (t == '0') { mint b, c; read(b, c); ds.act(l, r, pair(b, c)); } else { prtln(ds.ask(l, r).first); } } }