test/yosupo/swag.test.cpp

• View this file on GitHub
• Last update: 2023-07-03 22:03:10+09:00
• Problem: https://judge.yosupo.jp/problem/queue_operate_all_composite

Depends on

• deque/sliding_window.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#include "../../deque/sliding_window.hpp"

using namespace std;
using llong = long long;

// const llong mod = 998244353;
#define mod (998244353ll)
SlidingWindow<pair<llong, llong>> swag([](auto l, auto r) {
    pair<llong, llong> ret;
    ret.first = l.first * r.first;
    ret.second = l.first * r.second + l.second;
    ret.first %= mod;
    ret.second %= mod;
    return ret;
});

int main() {
    llong q;
    llong com;
    llong a, b;
    llong x;

    cin >> q;

    while (q--) {
        cin >> com;

        if (com == 0) {
            cin >> a >> b;
            swag.push_front({a, b});
        } else if (com == 1) {
            swag.pop_back();
        } else if (com == 2) {
            cin >> x;

            if (swag.empty()) {
                cout << x << '\n';
            } else {
                auto f = swag.fold();
                cout << (f.first * x + f.second) % mod << '\n';
            }
        }
    }
    return 0;
};

#line 1 "test/yosupo/swag.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#line 1 "deque/sliding_window.hpp"
#include <cassert>
#line 6 "deque/sliding_window.hpp"

//===
// LIBRARY SECTION

// #include <stack>
// #include <cassert>
template <class SemiGroup,
          class OP = std::function<SemiGroup(SemiGroup, SemiGroup)> >
struct SlidingWindow {
    // first:original data, second:sum
    using Stack = std::stack<std::pair<SemiGroup, SemiGroup> >;
    const OP merge;

    Stack front_st, back_st;

    SlidingWindow(const OP &f) : merge(f){};

    inline SemiGroup fold() {
        assert(!empty());

        if (front_st.empty())
            return back_st.top().second;
        else if (back_st.empty())
            return front_st.top().second;
        else
            return merge(front_st.top().second, back_st.top().second);
    };

    inline void push_front(SemiGroup d) {
        if (front_st.empty())
            front_st.emplace(d, d);
        else
            front_st.emplace(d, merge(d, front_st.top().second));
    };

    inline void push_back(SemiGroup d) {
        if (back_st.empty())
            back_st.emplace(d, d);
        else
            back_st.emplace(d, merge(back_st.top().second, d));
    };

    void pop_front() {
        assert(!empty());

        if (front_st.empty()) {
            Stack buff;
            while (buff.size() + 1 < back_st.size()) {
                buff.push(back_st.top());
                back_st.pop();
            }

            while (!back_st.empty()) {
                push_front(back_st.top().first);
                back_st.pop();
            }

            while (!buff.empty()) {
                push_back(buff.top().first);
                buff.pop();
            }
        }
        front_st.pop();
    };

    void pop_back() {
        assert(!empty());

        if (back_st.empty()) {
            Stack buff;
            while (buff.size() + 1 < front_st.size()) {
                buff.push(front_st.top());
                front_st.pop();
            }

            while (!front_st.empty()) {
                push_back(front_st.top().first);
                front_st.pop();
            }

            while (!buff.empty()) {
                push_front(buff.top().first);
                buff.pop();
            }
        }
        back_st.pop();
    };

    inline bool empty() {
        return size() == 0;
    };

    inline size_t size() {
        return front_st.size() + back_st.size();
    };
};
//===
#line 17 "test/yosupo/swag.test.cpp"

using namespace std;
using llong = long long;

// const llong mod = 998244353;
#define mod (998244353ll)
SlidingWindow<pair<llong, llong>> swag([](auto l, auto r) {
    pair<llong, llong> ret;
    ret.first = l.first * r.first;
    ret.second = l.first * r.second + l.second;
    ret.first %= mod;
    ret.second %= mod;
    return ret;
});

int main() {
    llong q;
    llong com;
    llong a, b;
    llong x;

    cin >> q;

    while (q--) {
        cin >> com;

        if (com == 0) {
            cin >> a >> b;
            swag.push_front({a, b});
        } else if (com == 1) {
            swag.pop_back();
        } else if (com == 2) {
            cin >> x;

            if (swag.empty()) {
                cout << x << '\n';
            } else {
                auto f = swag.fold();
                cout << (f.first * x + f.second) % mod << '\n';
            }
        }
    }
    return 0;
};

Back to top page