Submit Info #28835

Problem Lang User Status Time Memory
Queue Operate All Composite cpp kaage AC 115 ms 13.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
example_01 AC 1 ms 0.65 MiB
large_max_00 AC 103 ms 9.69 MiB
large_max_01 AC 100 ms 9.61 MiB
large_min_00 AC 84 ms 2.25 MiB
large_min_01 AC 85 ms 2.23 MiB
large_triangle_00 AC 85 ms 3.30 MiB
large_triangle_01 AC 83 ms 3.37 MiB
max_random_00 AC 113 ms 13.81 MiB
max_random_01 AC 113 ms 13.88 MiB
max_random_02 AC 115 ms 13.78 MiB
random_00 AC 74 ms 4.68 MiB
random_01 AC 89 ms 5.55 MiB
random_02 AC 10 ms 1.19 MiB
small_00 AC 1 ms 0.65 MiB
small_01 AC 2 ms 0.66 MiB
small_02 AC 3 ms 0.62 MiB
small_03 AC 1 ms 0.61 MiB
small_04 AC 1 ms 0.68 MiB

#line 1 "test/yosupo/queue_operate_all_composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #line 2 "other/template.hpp" #define _CRT_SECURE_NO_WARNINGS #pragma target("avx2") #pragma optimize("O3") #pragma optimize("unroll-loops") #include <algorithm> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <string.h> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=1;i<=(n);i++) #define all(V) V.begin(),V.end() typedef unsigned int uint; typedef long long lint; typedef unsigned long long ulint; typedef std::pair<int, int> P; typedef std::pair<lint, lint> LP; constexpr int INF = INT_MAX/2; constexpr lint LINF = LLONG_MAX/2; constexpr double eps = DBL_EPSILON; constexpr double PI=3.141592653589793238462643383279; template<class T> class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {}; template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } inline lint gcd(lint a, lint b) { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) { return a / gcd(a, b) * b; } bool isprime(lint n) { if (n == 1)return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0)return false; } return true; } template<typename T> T mypow(T a, lint b) { T res(1); while(b){ if(b&1)res*=a; a*=a; b>>=1; } return res; } lint modpow(lint a, lint b, lint m) { lint res(1); while(b){ if(b&1){ res*=a;res%=m; } a*=a;a%=m; b>>=1; } return res; } template<typename T> void printArray(std::vector<T>& vec) { rep(i, vec.size()){ std::cout << vec[i]; std::cout<<(i==(int)vec.size()-1?"\n":" "); } } template<typename T> void printArray(T l, T r) { T rprev = std::prev(r); for (T i = l; i != rprev; i++) { std::cout << *i << " "; } std::cout << *rprev << std::endl; } LP extGcd(lint a,lint b) { if(b==0)return {1,0}; LP s=extGcd(b,a%b); std::swap(s.first,s.second); s.second-=a/b*s.first; return s; } LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) { lint p=extGcd(m1,m2).first; lint tmp=(b2-b1)*p%m2; lint r=(b1+m1*tmp+m1*m2)%(m1*m2); return std::make_pair(r,m1*m2); } template<typename F> inline constexpr decltype(auto) lambda_fix(F&& f){ return [f=std::forward<F>(f)](auto&&... args){ return f(f,std::forward<decltype(args)>(args)...); }; } #line 3 "algebraic/DynamicModInt.hpp" class DynamicModInt { lint value; public: static unsigned int modulo; DynamicModInt() : value(0) {} template<typename T> DynamicModInt(T value = 0) : value(value) { if (value < 0)value = -(lint)(-value % modulo) + modulo; this->value = value % modulo; } static inline void setMod(const unsigned int& mod){modulo=mod;} inline DynamicModInt inv()const{return mypow(*this,modulo-2);} inline operator int()const { return value; } inline DynamicModInt& operator+=(const DynamicModInt& x) { value += x.value; if (value >= modulo)value -= modulo; return *this; } inline DynamicModInt& operator++() { if (value == modulo - 1)value = 0; else value++; return *this; } inline DynamicModInt operator++(int){ DynamicModInt res=*this; --*this; return res; } inline DynamicModInt operator-()const { return DynamicModInt(0) -= *this; } inline DynamicModInt& operator-=(const DynamicModInt& x) { value -= x.value; if (value < 0)value += modulo; return *this; } inline DynamicModInt& operator--() { if (value == 0)value = modulo - 1; else value--; return *this; } inline DynamicModInt operator--(int){ DynamicModInt res=*this; --*this; return res; } inline DynamicModInt& operator*=(const DynamicModInt& x) { value = value * x.value % modulo; return *this; } inline DynamicModInt& operator/=(const DynamicModInt& rhs) { return *this*=rhs.inv(); } template<typename T> DynamicModInt operator+(const T& rhs)const { return DynamicModInt(*this) += rhs; } template<typename T> DynamicModInt& operator+=(const T& rhs) { return operator+=(DynamicModInt(rhs)); } template<typename T> DynamicModInt operator-(const T& rhs)const { return DynamicModInt(*this) -= rhs; } template<typename T> DynamicModInt& operator-=(const T& rhs) { return operator-=(DynamicModInt(rhs)); } template<typename T> DynamicModInt operator*(const T& rhs)const { return DynamicModInt(*this) *= rhs; } template<typename T> DynamicModInt& operator*=(const T& rhs) { return operator*=(DynamicModInt(rhs)); } template<typename T> DynamicModInt operator/(const T& rhs)const { return DynamicModInt(*this) /= rhs; } template<typename T> DynamicModInt& operator/=(const T& rhs) { return operator/=(DynamicModInt(rhs)); } }; unsigned int DynamicModInt::modulo=1000000007; std::istream& operator>>(std::istream& ist, DynamicModInt& x) { lint a; ist >> a; x = a; return ist; } #line 4 "algebraic/StaticModInt.hpp" template<unsigned int modulo> class StaticModInt { lint value; public: static constexpr unsigned int mod_value = modulo; StaticModInt() : value(0) {} template<typename T> StaticModInt(T value = 0) : value(value) { if (value < 0)value = -(lint)(-value % modulo) + modulo; this->value = value % modulo; } inline StaticModInt inv()const{return mypow(*this,modulo-2);} inline operator int()const { return value; } inline StaticModInt& operator+=(const StaticModInt& x) { value += x.value; if (value >= modulo)value -= modulo; return *this; } inline StaticModInt& operator++() { if (value == modulo - 1)value = 0; else value++; return *this; } inline StaticModInt operator++(int){ StaticModInt res=*this; --*this; return res; } inline StaticModInt operator-()const { return StaticModInt(0) -= *this; } inline StaticModInt& operator-=(const StaticModInt& x) { value -= x.value; if (value < 0)value += modulo; return *this; } inline StaticModInt& operator--() { if (value == 0)value = modulo - 1; else value--; return *this; } inline StaticModInt operator--(int){ StaticModInt res=*this; --*this; return res; } inline StaticModInt& operator*=(const StaticModInt& x) { value = value * x.value % modulo; return *this; } inline StaticModInt& operator/=(const StaticModInt& rhs) { return *this*=rhs.inv(); } template<typename T> StaticModInt operator+(const T& rhs)const { return StaticModInt(*this) += rhs; } template<typename T> StaticModInt& operator+=(const T& rhs) { return operator+=(StaticModInt(rhs)); } template<typename T> StaticModInt operator-(const T& rhs)const { return StaticModInt(*this) -= rhs; } template<typename T> StaticModInt& operator-=(const T& rhs) { return operator-=(StaticModInt(rhs)); } template<typename T> StaticModInt operator*(const T& rhs)const { return StaticModInt(*this) *= rhs; } template<typename T> StaticModInt& operator*=(const T& rhs) { return operator*=(StaticModInt(rhs)); } template<typename T> StaticModInt operator/(const T& rhs)const { return StaticModInt(*this) /= rhs; } template<typename T> StaticModInt& operator/=(const T& rhs) { return operator/=(StaticModInt(rhs)); } }; template<unsigned int modulo> std::istream& operator>>(std::istream& ist, StaticModInt<modulo>& x) { lint a; ist >> a; x = a; return ist; } #line 3 "data-structure/SWAG.hpp" template<typename T,T (*op)(T,T)> class SWAG{ std::stack<std::pair<T,T>> front,back; public: SWAG(){} SWAG(const std::vector<T> vec){ for(const T& i:vec){ back.emplace(i,op(back.top().second,i)); } } void push(const T& x){ if(back.empty())back.emplace(x,x); else back.emplace(x,op(back.top().second,x)); } void pop(){ if(!front.empty())front.pop(); else{ front.emplace(back.top().first,back.top().first); back.pop(); while(!back.empty()){ front.emplace(back.top().first,op(back.top().first,front.top().second)); back.pop(); } front.pop(); } } T fold()const{ if(front.empty())return back.top().second; if(back.empty())return front.top().second; return op(front.top().second,back.top().second); } unsigned int size()const{return front.size()+back.size();} bool empty()const{return front.empty()&&back.empty();} }; #line 5 "test/yosupo/queue_operate_all_composite.test.cpp" using ModInt=StaticModInt<998244353>; using MP=std::pair<ModInt,ModInt>; MP op(MP lhs,MP rhs){ return MP{lhs.first*rhs.first,lhs.second*rhs.first+rhs.second}; } int Q; int main(){ scanf("%d",&Q); SWAG<MP,op> swag; rep(i,Q){ int t; scanf("%d",&t); if(t==0){ int a,b; scanf("%d%d",&a,&b); swag.push(MP{a,b}); } if(t==1)swag.pop(); if(t==2){ int x; scanf("%d",&x); if(swag.empty())printf("%d\n",x); else{ auto res=swag.fold(); printf("%d\n",res.first*x+res.second); } } } }