src/test/yosupo_queue_operate_all_composite.cpp

• View this file on GitHub
• Last update: 2025-12-30 15:03:15+09:00
• Problem: https://judge.yosupo.jp/problem/queue_operate_all_composite

Depends on

• src/math/modint.hpp
• src/structure/swag.hpp
• src/template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
#include "../structure/swag.hpp"
#include "../math/modint.hpp"

using mint=modint<>;
using S=pair<mint,mint>;
S op(S l,S r){return {l.fi*r.fi,l.se*r.fi+r.se};}
S e(){return {1,0};}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin>>Q;

    vector<pair<mint,mint>> R,LD,RD;
    SWAG<S,op,e> swag;
    while(Q--){
        int o;
        cin>>o;
        if(o==0){
            int a,b;
            cin>>a>>b;
            swag.push({a,b});
        }
        else if(o==1){
            swag.pop();
        }
        else{
            long x;
            cin>>x;
            S s=swag.get();
            mint ans=s.fi*x+s.se;
            cout<<ans<<"\n";
        }

    }
}

#line 1 "src/test/yosupo_queue_operate_all_composite.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/swag.hpp"

template<class S,S (*op)(S,S),S (*e)()>
struct SWAG {
    vector<S> r,ld,rd;
    SWAG():r(1,e()),ld(1,e()),rd(1,e()){}

    void push(S s){
        r.push_back(s);
        rd.push_back(op(rd.back(),s));
    }
    void pop(){
        if(si(ld)==1){
            while(si(r)>=2){
                ld.push_back(op(r.back(),ld.back()));
                r.pop_back();
                rd.pop_back();
            }
        }
        ld.pop_back();
        assert(si(ld));
    }
    S get(){
        return op(ld.back(),rd.back());
    }
    pair<S,S> get_lr(){
        return {ld.back(),rd.back()};
    }
};

#line 3 "src/math/modint.hpp"

template<int mod=998244353> struct modint {
    int x;
    constexpr modint(long long x_=0):x(((x_%mod)+mod)%mod){}
    constexpr modint operator-(){
        auto res=*this;
        res.x=(x?mod-x:0);
        return res;
    }
    constexpr modint& operator+=(modint r){
        if((x+=r.x)>=mod) x-=mod;
        return *this;
    }
    constexpr modint& operator-=(modint r){
        if((x-=r.x)<0) x+=mod;
        return *this;
    }
    constexpr modint& operator*=(modint r){
        x=1ll*x*r.x%mod;
        return *this;
    }
    constexpr modint& operator/=(modint r){return *this*=r.inv();}
    constexpr friend modint operator+(modint a,modint b){return a+=b;}
    constexpr friend modint operator-(modint a,modint b){return a-=b;}
    constexpr friend modint operator*(modint a,modint b){return a*=b;}
    constexpr friend modint operator/(modint a,modint b){return a/=b;}
    constexpr modint inv() const {return pow(mod-2);}
    constexpr modint pow(long long b) const {
        assert(0<=b);
        modint a=*this,c=1;
        while(b){
            if(b&1) c*=a;
            a*=a;
            b>>=1;
        }
        return c;
    }
    constexpr int val() const {return x;}
    constexpr friend ostream& operator<<(ostream& os,const modint& m){return os<<m.val();}
    constexpr friend istream& operator>>(istream& is,modint& m){
        long long v;
        is>>v;
        m=modint(v);
        return is;
    }
};
#line 4 "src/test/yosupo_queue_operate_all_composite.cpp"

using mint=modint<>;
using S=pair<mint,mint>;
S op(S l,S r){return {l.fi*r.fi,l.se*r.fi+r.se};}
S e(){return {1,0};}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin>>Q;

    vector<pair<mint,mint>> R,LD,RD;
    SWAG<S,op,e> swag;
    while(Q--){
        int o;
        cin>>o;
        if(o==0){
            int a,b;
            cin>>a>>b;
            swag.push({a,b});
        }
        else if(o==1){
            swag.pop();
        }
        else{
            long x;
            cin>>x;
            S s=swag.get();
            mint ans=s.fi*x+s.se;
            cout<<ans<<"\n";
        }

    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	4 MB
g++	example_01	AC	5 ms	4 MB
g++	large_max_00	AC	159 ms	11 MB
g++	large_max_01	AC	161 ms	10 MB
g++	large_min_00	AC	123 ms	4 MB
g++	large_min_01	AC	121 ms	4 MB
g++	large_triangle_00	AC	122 ms	5 MB
g++	large_triangle_01	AC	122 ms	5 MB
g++	max_random_00	AC	161 ms	12 MB
g++	max_random_01	AC	162 ms	13 MB
g++	max_random_02	AC	167 ms	12 MB
g++	random_00	AC	107 ms	6 MB
g++	random_01	AC	137 ms	6 MB
g++	random_02	AC	19 ms	4 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB

Back to top page