This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#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; };