Submit Info #60728

Problem Lang User Status Time Memory
Queue Operate All Composite cpp (anonymous) AC 360 ms 13.57 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.45 MiB
large_max_00 AC 303 ms 9.41 MiB
large_max_01 AC 306 ms 9.35 MiB
large_min_00 AC 281 ms 1.88 MiB
large_min_01 AC 282 ms 1.95 MiB
large_triangle_00 AC 281 ms 3.05 MiB
large_triangle_01 AC 282 ms 3.04 MiB
max_random_00 AC 357 ms 13.57 MiB
max_random_01 AC 358 ms 13.53 MiB
max_random_02 AC 360 ms 13.50 MiB
random_00 AC 229 ms 4.45 MiB
random_01 AC 274 ms 5.24 MiB
random_02 AC 32 ms 0.89 MiB
small_00 AC 1 ms 0.45 MiB
small_01 AC 1 ms 0.45 MiB
small_02 AC 1 ms 0.42 MiB
small_03 AC 1 ms 0.45 MiB
small_04 AC 1 ms 0.45 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #include<bits/stdc++.h> using namespace std; template<class T> class SWAG { class Node { public: T val,sum; Node(const T& val,const T& sum) : val(val),sum(sum) {} }; std::stack<Node> front_stack,back_stack; function<T(T,T)> op; public: SWAG(const auto op) : op(op) {} bool empty() { return front_stack.empty() && back_stack.empty(); } T fold_all() { assert(!empty()); if(front_stack.empty()) { return back_stack.top().sum; } else if(back_stack.empty()) { return front_stack.top().sum; } else { return op(front_stack.top().sum,back_stack.top().sum); } } void push(T x) { if(back_stack.empty()) back_stack.emplace(x,x); else back_stack.emplace(x,op(back_stack.top().sum,x)); } void pop() { assert(!empty()); if(front_stack.empty()) { front_stack.emplace(back_stack.top().val,back_stack.top().val); back_stack.pop(); while(!back_stack.empty()) { T tmp{op(back_stack.top().val,front_stack.top().sum)}; front_stack.emplace(back_stack.top().val,tmp); back_stack.pop(); } } front_stack.pop(); } }; constexpr long long MOD = 998244353; using S = pair<long long,long long>; S op(S A,S B) { return {A.first * B.first % MOD,(B.first * A.second + B.second) % MOD}; } int main() { int Q; cin >> Q; SWAG<S> swag(op); for(int i = 0;i < Q;i++) { int q; cin >> q; if(q == 0) { long long a,b; cin >> a >> b; swag.push({a,b}); } else if(q == 1) { swag.pop(); } else { long long x; cin >> x; if(swag.empty()) cout << x << endl; else { S res = swag.fold_all(); cout << (res.first * x + res.second) % MOD << endl; } } } }