Submit Info #54728

Problem Lang User Status Time Memory
Queue Operate All Composite cpp-acl Kude AC 100 ms 7.80 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.71 MiB
example_01 AC 1 ms 0.61 MiB
large_max_00 AC 88 ms 7.44 MiB
large_max_01 AC 88 ms 7.55 MiB
large_min_00 AC 71 ms 2.21 MiB
large_min_01 AC 71 ms 2.22 MiB
large_triangle_00 AC 70 ms 3.09 MiB
large_triangle_01 AC 71 ms 3.08 MiB
max_random_00 AC 100 ms 7.80 MiB
max_random_01 AC 98 ms 7.79 MiB
max_random_02 AC 99 ms 7.79 MiB
random_00 AC 62 ms 3.57 MiB
random_01 AC 75 ms 4.56 MiB
random_02 AC 9 ms 1.20 MiB
small_00 AC 1 ms 0.61 MiB
small_01 AC 1 ms 0.71 MiB
small_02 AC 1 ms 0.61 MiB
small_03 AC 1 ms 0.61 MiB
small_04 AC 1 ms 0.71 MiB

#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; using mint = modint998244353; template <class S, S (*op)(S, S), S (*e)()> struct SWAG { std::vector<S> ar, sl, sr; SWAG() : sl{e()}, sr{e()} {} explicit SWAG(const std::vector<S>& v) : sr{e()} { const int n = v.size(); S x = e(); sl.reserve(n + 1); sl.push_back(x); for (int i = n - 1; i >= 0; i--) { x = op(v[i], x); sl.push_back(x); } } void push(S x) { ar.push_back(x); sr.push_back(op(sr.back(), x)); } void pop() { assert(sl.size() != 1 || ar.size() != 0); if (sl.size() != 1) { sl.pop_back(); } else { const int n = ar.size(); S x = e(); for (int i = n - 1; i >= 1; i--) { x = op(ar[i], x); sl.push_back(x); } ar.resize(0); sr.resize(1); } } S all_prod() { return op(sl.back(), sr.back()); } int size() { return (int)sl.size() - 1 + ar.size(); } }; using S = pair<mint, mint>; S op(S x, S y) { auto [a, b] = x; auto [c, d] = y; return {a * c, c * b + d}; } S e() { return {1, 0}; } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; SWAG<S, op, e> sw; while(q--) { int t; cin >> t; if (t == 0) { int a, b; cin >> a >> b; sw.push({a, b}); } else if (t == 1) { sw.pop(); } else { int x; cin >> x; auto [a, b] = sw.all_prod(); mint ans = a * x + b; cout << ans.val() << '\n'; } } }