test/ds/swag.test.cpp

• View this file on GitHub
• Last update: 2024-06-21 05:23:41+09:00
• Problem: https://judge.yosupo.jp/problem/queue_operate_all_composite

Depends on

• ds/Swag.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"

#include "../..//ds/Swag.hpp"

#include <vector>
#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;
using F = std::pair<mint, mint>;
F e(){
    return {1, 0};
}

F op(F l, F r){
    return {l.first * r.first, l.second * r.first + r.second};
}

int main(){
    int Q;
    std::cin >> Q;
    po167::SWAG<F, op, e> S(Q);
    while (Q--){
        int t;
        std::cin >> t;
        if (t == 0){
            int a, b;
            std::cin >> a >> b;
            S.push({a, b});
        }
        if (t == 1){
            S.pop();
        }
        if (t == 2){
            int x;
            std::cin >> x;
            F tmp = S.calc();
            std::cout << (tmp.first * x + tmp.second).val() << "\n";
        }
    }
}

#line 1 "test/ds/swag.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"

#line 2 "ds/Swag.hpp"
#include <vector>
#include <cassert>

namespace po167{
template<class T, T (*op)(T, T), T (*e)()>
struct SWAG
{
    std::vector<std::pair<T, T>> A, B;
    SWAG(int n = -1){
        if (n > 0) A.reserve(n + 1), B.reserve(n + 1);
        A.push_back({e(), e()});
        B.push_back({e(), e()});
    }
    void push(T v){
        B.push_back({v, op(B.back().second, v)});
    }
    void pop(){
        if ((int)A.size() == 1){
            while ((int)B.size() != 1){
                A.push_back({B.back().first, op(B.back().first, A.back().second)});
                B.pop_back();
            }
        }
        assert((int)A.size() != 1);
        A.pop_back();
    }
    T calc(){
        return op(A.back().second, B.back().second);
    }
};
}
#line 4 "test/ds/swag.test.cpp"

#line 6 "test/ds/swag.test.cpp"
#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;
using F = std::pair<mint, mint>;
F e(){
    return {1, 0};
}

F op(F l, F r){
    return {l.first * r.first, l.second * r.first + r.second};
}

int main(){
    int Q;
    std::cin >> Q;
    po167::SWAG<F, op, e> S(Q);
    while (Q--){
        int t;
        std::cin >> t;
        if (t == 0){
            int a, b;
            std::cin >> a >> b;
            S.push({a, b});
        }
        if (t == 1){
            S.pop();
        }
        if (t == 2){
            int x;
            std::cin >> x;
            F tmp = S.calc();
            std::cout << (tmp.first * x + tmp.second).val() << "\n";
        }
    }
}

Back to top page