Submit Info #58100

Problem Lang User Status Time Memory
Queue Operate All Composite cpp tomo0608 AC 382 ms 12.54 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 301 ms 12.44 MiB
large_max_01 AC 338 ms 12.54 MiB
large_min_00 AC 279 ms 5.73 MiB
large_min_01 AC 280 ms 5.67 MiB
large_triangle_00 AC 278 ms 6.05 MiB
large_triangle_01 AC 278 ms 5.95 MiB
max_random_00 AC 382 ms 9.28 MiB
max_random_01 AC 351 ms 9.28 MiB
max_random_02 AC 352 ms 9.37 MiB
random_00 AC 229 ms 5.96 MiB
random_01 AC 267 ms 5.97 MiB
random_02 AC 31 ms 1.07 MiB
small_00 AC 1 ms 0.45 MiB
small_01 AC 1 ms 0.40 MiB
small_02 AC 1 ms 0.43 MiB
small_03 AC 1 ms 0.45 MiB
small_04 AC 1 ms 0.45 MiB

#include<iostream> #include<vector> #include<stack> #include<cassert> template<class Monoid, Monoid(*op)(Monoid, Monoid), Monoid(*e)()> struct SWAG{ SWAG():l(0),r(0),last_i(0),last_j(0),front(e()),v(0),back(){} explicit SWAG(std::vector<Monoid> &_v):l(0),r(0),last_i(0), last_j(0), front(e()),v(_v.size()),back(){ std::copy(_v.begin(),_v.end(), v.begin()); } void push_back(const Monoid &c){ v.push_back(c); } size_t size(){ return v.size(); } Monoid fold(size_t i, size_t j){ //[l, r) assert(i < j && j <= v.size()); assert(last_i <= i && last_j <= j); last_i = i, last_j = j; while(r < j)front = op(front, v[r++]); while(l < i){ if(back.empty()){ Monoid tmp = e(); for(size_t u = r; u-- > l; ){ tmp = op(v[u], tmp); back.emplace(tmp); } front = e(); } back.pop(); ++l; } if(back.empty())return front; return op(back.top(), front); } private: std::vector<Monoid> v; Monoid front; std::stack<Monoid> back; size_t l, r, last_i, last_j; }; using namespace std; #define ll long long const ll MOD = 998244353; #define S pair<ll,ll> S op(S x, S y){ S z; z.first = x.first * y.first % MOD; z.second = (y.first * x.second + y.second)%MOD; return z; } S e(){return {1, 0};} int main(){ int q;cin >> q; int l = 0, r = 0; SWAG<S, op, e> swag; while(q--){ int i;cin >> i; if(i == 0){ ll a,b;cin >> a >> b; swag.push_back(S(a, b)); r++; } if(i == 1){ l++; } if(i == 2){ ll x;cin >> x; if(l == r){ cout << x << endl; continue; } auto [a,b] = swag.fold(l, r); ll fx = (a*x + b)%MOD; cout << fx << endl; } } }