Submit Info #2592

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

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.59 MiB
example_01 AC 6 ms 0.55 MiB
large_max_00 AC 117 ms 9.68 MiB
large_max_01 AC 117 ms 9.62 MiB
large_min_00 AC 100 ms 2.25 MiB
large_min_01 AC 102 ms 2.23 MiB
large_triangle_00 AC 102 ms 3.38 MiB
large_triangle_01 AC 101 ms 3.31 MiB
max_random_00 AC 131 ms 13.84 MiB
max_random_01 AC 128 ms 13.83 MiB
max_random_02 AC 132 ms 13.80 MiB
random_00 AC 88 ms 4.76 MiB
random_01 AC 103 ms 5.55 MiB
random_02 AC 16 ms 1.12 MiB
small_00 AC 6 ms 0.64 MiB
small_01 AC 5 ms 0.64 MiB
small_02 AC 5 ms 0.55 MiB
small_03 AC 6 ms 0.55 MiB
small_04 AC 6 ms 0.67 MiB

#define _GLIBCXX_DEBUG #include <bits/stdc++.h> #define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i)) #define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i)) #define rep(i, n) For((i), 0, (n)) #define rrep(i, n) rFor((i), (n), 0) #define fi first #define se second using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair<int, int> pii; typedef pair<lint, int> pli; typedef pair<lint, lint> pll; typedef complex<double> xy_t; template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;} template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;} constexpr lint mod = 998244353; constexpr lint INF = mod*mod; constexpr int MAX = 1000000; template<class T> struct SWAG{ using P = pair<T, T>; stack<P> st_front, st_back; function<T(T, T)> f; SWAG(function<T(T, T)> f_): f(f_){} int size(){ return st_front.size() + st_back.size(); } T fold_all(){ if(st_front.empty()) return st_back.top().se; if(st_back.empty()) return st_front.top().se; return f(st_front.top().se, st_back.top().se); } void push(T a){ if(st_back.empty()) st_back.emplace(a, a); else st_back.emplace(a, f(st_back.top().se, a)); } void pop(){ if(!size()) return; if(!st_front.empty()) st_front.pop(); else{ while(!st_back.empty()){ P tmp=st_back.top(); if(st_front.empty()){ st_front.emplace(tmp.fi, tmp.fi); st_back.pop(); } else{ st_front.emplace(tmp.fi, f(tmp.fi, st_front.top().se)); st_back.pop(); } } st_front.pop(); } } }; int main(){ int q; scanf("%d", &q); auto f=[&](pll a, pll b){ return make_pair(b.fi*a.fi%mod, (b.fi*a.se+b.se)%mod); }; SWAG<pll> sw(f); while(q--){ int c; scanf("%d", &c); if(c==0){ lint a, b; scanf("%lld%lld", &a, &b); sw.push({a, b}); } if(c==1) sw.pop(); if(c==2){ lint x; scanf("%lld", &x); if(sw.size()==0){ printf("%lld\n", x); continue; } pll a=sw.fold_all(); printf("%lld\n", (a.fi*x+a.se)%mod); } } }