Submit Info #53077

Problem Lang User Status Time Memory
Queue Operate All Composite cpp Forested AC 344 ms 4.84 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
example_01 AC 1 ms 0.37 MiB
large_max_00 AC 283 ms 3.58 MiB
large_max_01 AC 280 ms 3.58 MiB
large_min_00 AC 269 ms 2.21 MiB
large_min_01 AC 270 ms 2.21 MiB
large_triangle_00 AC 270 ms 2.46 MiB
large_triangle_01 AC 269 ms 2.46 MiB
max_random_00 AC 335 ms 4.84 MiB
max_random_01 AC 334 ms 4.84 MiB
max_random_02 AC 344 ms 4.84 MiB
random_00 AC 216 ms 2.34 MiB
random_01 AC 258 ms 2.70 MiB
random_02 AC 31 ms 0.84 MiB
small_00 AC 1 ms 0.61 MiB
small_01 AC 1 ms 0.61 MiB
small_02 AC 1 ms 0.59 MiB
small_03 AC 1 ms 0.61 MiB
small_04 AC 1 ms 0.61 MiB

// ----- "sliding_window_aggregation.hpp" ----- #ifndef SLIDING_WINDOW_AGGREGATION_HPP #define SLIDING_WINDOW_AGGREGATION_HPP #include <stack> #include <cassert> #include <utility> template <typename Op> class SlidingWindowAggregation { public: using Value = typename Op::Value; private: std::stack<Value> st0; std::stack<Value> st1; Value st1_sum; public: SlidingWindowAggregation() : st0({Op::id()}), st1({Op::id()}), st1_sum(Op::id()) {} void push(Value val) { st1_sum = Op::op(st1_sum, val); st1.emplace(std::move(val)); } void pop() { if (st0.size() == 1) { while (st1.size() > 1) { st0.emplace(Op::op(st1.top(), st0.top())); st1.pop(); } st1_sum = Op::id(); } st0.pop(); } std::size_t size() const { return st0.size() + st1.size() - 2; } bool empty() const { return size() == 0; } Value sum() const { return Op::op(st0.top(), st1_sum); } }; #endif // ----- "sliding_window_aggregation.hpp" ----- // ----- "mod_int.hpp" ----- #ifndef MOD_INT_HPP #define MOD_INT_HPP #include <cassert> #include <type_traits> #include <iostream> // ----- "utils.hpp" ----- #ifndef UTILS_HPP #define UTILS_HPP #include <cstddef> constexpr bool is_prime(unsigned n) { if (n == 0 || n == 1) return false; for (unsigned i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) { unsigned ret = 1, self = x; while (y != 0) { if (y & 1) ret = (unsigned long long) ret * self % mod; self = (unsigned long long) self * self % mod; y >>= 1; } return ret; } template <unsigned mod> constexpr unsigned primitive_root() { static_assert(is_prime(mod), "`mod` must be a prime number."); if (mod == 2) return 1; unsigned primes[32] = {}; std::size_t it = 0; { unsigned m = mod - 1; for (unsigned i = 2; i * i <= m; ++i) { if (m % i == 0) { primes[it++] = i; while (m % i == 0) m /= i; } } if (m != 1) primes[it++] = m; } for (unsigned i = 2; i < mod; ++i) { bool ok = true; for (std::size_t j = 0; j < it; ++j) { if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) { ok = false; break; } } if (ok) return i; } return 0; } #endif // ----- "utils.hpp" ----- template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr> constexpr unsigned safe_mod(T x, unsigned mod) { if (x < 0) { return (unsigned) (x % mod + mod); } else { return (unsigned) (x % mod); } } template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr> constexpr unsigned safe_mod(T x, unsigned mod) { return (unsigned) (x % mod); } template <unsigned mod> class ModInt { static_assert(mod != 0, "`mod` must not be equal to 0."); static_assert(mod < (1u << 31), "`mod` must be less than (1u << 31) = 2147483648."); unsigned val; public: constexpr ModInt() : val(0) {} template <typename T> constexpr ModInt(T x) : val(safe_mod(x, mod)) {} static constexpr ModInt raw(unsigned x) { ModInt<mod> ret; ret.val = x; return ret; } constexpr unsigned get_val() const { return val; } constexpr ModInt operator+() const { return *this; } constexpr ModInt operator-() const { return ModInt<mod>(0u) - *this; } constexpr ModInt &operator+=(const ModInt &rhs) { val += rhs.val; if (val >= mod) val -= mod; return *this; } constexpr ModInt &operator-=(const ModInt &rhs) { if (val < rhs.val) val += mod; val -= rhs.val; return *this; } constexpr ModInt &operator*=(const ModInt &rhs) { val = (unsigned long long) val * rhs.val % mod; return *this; } constexpr ModInt &operator/=(const ModInt &rhs) { val = (unsigned long long) val * rhs.inv().val % mod; return *this; } friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) += rhs; } friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) -= rhs; } friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) *= rhs; } friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) { return ModInt<mod>(lhs) /= rhs; } constexpr ModInt pow(unsigned x) const { ModInt<mod> ret = ModInt<mod>::raw(1); ModInt<mod> self = *this; while (x != 0) { if (x & 1) ret *= self; self *= self; x >>= 1; } return ret; } constexpr ModInt inv() const { static_assert(is_prime(mod), "`mod` must be a prime number."); assert(val != 0); return this->pow(mod - 2); } friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) { is >> x.val; // x.val %= mod; return is; } friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) { os << x.val; return os; } friend bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val == rhs.val; } }; #endif // ----- "mod_int.hpp" ----- // ----- "linear_function.hpp" ----- #ifndef LINEAR_FUNCTION_HPP #define LINEAR_FUNCTION_HPP template <typename T> struct LinearFunction { T slope; T intercept; LinearFunction() : slope(), intercept() {} LinearFunction(const T &s, const T &i) : slope(s), intercept(i) {} T operator()(const T &x) const { return intercept + slope * x; } // (this)(other(x)) LinearFunction<T> composite(const LinearFunction<T> &other) const { return LinearFunction<T>(slope * other.slope, slope * other.intercept + intercept); } }; #endif // ----- "linear_function.hpp" ----- constexpr unsigned mod = 998244353; using Mint = ModInt<mod>; using LF = LinearFunction<Mint>; struct LFC { using Value = LF; static Value id() { return LF(Mint(1), Mint(0)); } static Value op(const Value &lhs, const Value &rhs) { return rhs.composite(lhs); } }; int main() { SlidingWindowAggregation<LFC> swag; std::size_t q; std::cin >> q; for (std::size_t _i = 0; _i < q; ++_i) { std::size_t type; std::cin >> type; if (type == 0) { LF f; std::cin >> f.slope >> f.intercept; swag.push(f); } else if (type == 1) { swag.pop(); } else { Mint x; std::cin >> x; std::cout << swag.sum()(x) << '\n'; } } }