結果
問題 | No.1084 積の積 |
ユーザー | beet |
提出日時 | 2020-06-19 21:40:59 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 4,571 bytes |
コンパイル時間 | 2,410 ms |
コンパイル使用メモリ | 214,824 KB |
実行使用メモリ | 13,124 KB |
最終ジャッジ日時 | 2023-09-16 13:43:49 |
合計ジャッジ時間 | 5,005 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 104 ms
12,004 KB |
testcase_05 | AC | 20 ms
13,124 KB |
testcase_06 | AC | 102 ms
11,988 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 24 ms
11,724 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | AC | 30 ms
6,808 KB |
testcase_13 | AC | 66 ms
11,136 KB |
testcase_14 | AC | 22 ms
5,812 KB |
testcase_15 | AC | 21 ms
5,396 KB |
testcase_16 | AC | 75 ms
11,992 KB |
testcase_17 | AC | 28 ms
6,552 KB |
testcase_18 | AC | 47 ms
8,184 KB |
testcase_19 | AC | 66 ms
11,460 KB |
testcase_20 | AC | 15 ms
4,592 KB |
testcase_21 | AC | 22 ms
5,464 KB |
testcase_22 | AC | 18 ms
5,256 KB |
testcase_23 | AC | 37 ms
7,444 KB |
testcase_24 | AC | 34 ms
7,148 KB |
testcase_25 | AC | 66 ms
11,056 KB |
testcase_26 | AC | 75 ms
12,012 KB |
testcase_27 | AC | 75 ms
12,316 KB |
testcase_28 | AC | 75 ms
12,144 KB |
testcase_29 | AC | 76 ms
12,084 KB |
testcase_30 | AC | 75 ms
12,000 KB |
testcase_31 | AC | 75 ms
12,008 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; template <typename E> struct SegmentTree{ using H = function<E(E,E)>; int n,height; H h; E ei; vector<E> laz; SegmentTree(H h,E ei):h(h),ei(ei){} void init(int n_){ n=1;height=0; while(n<n_) n<<=1,height++; laz.assign(2*n,ei); } inline void propagate(int k){ if(laz[k]==ei) return; laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]); laz[k]=ei; } inline void thrust(int k){ for(int i=height;i;i--) propagate(k>>i); } void update(int a,int b,E x){ if(a>=b) return; thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l<r;l>>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } } E get_val(int a){ thrust(a+=n); return laz[a]; } void set_val(int a,E x){ thrust(a+=n); laz[a]=x; } }; template<typename T,T MOD = 1000000007> struct Mint{ static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v <a.v;} static Mint comb(long long n,int k){ Mint num(1),dom(1); for(int i=0;i<k;i++){ num*=Mint(n-i); dom*=Mint(i+1); } return num/dom; } }; template<typename T,T MOD> constexpr T Mint<T, MOD>::mod; template<typename T,T MOD> ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T> struct DisjointSparseTable{ using F = function<T(T, T)>; vector< vector<T> > dat; vector<int> ht; const F f; DisjointSparseTable(){} DisjointSparseTable(F f):f(f){} void build(const vector<T> &vs){ int n=vs.size(),h=1; while((1<<h)<=n) h++; dat.assign(h,vector<T>(n)); ht.assign((1<<h)+1,0); for(int j=2;j<(1<<h)+1;j++) ht[j]=ht[j>>1]+1; for(int j=0;j<n;j++) dat[0][j]=vs[j]; for(int i=1;i<h;i++){ int s=1<<i; for(int j=0;j<n;j+=s<<1){ int t=min(j+s,n); dat[i][t-1]=vs[t-1]; for(int k=t-2;k>=j;k--) dat[i][k]=f(vs[k],dat[i][k+1]); if(n<=t) break; dat[i][t]=vs[t]; int r=min(t+s,n); for(int k=t+1;k<r;k++) dat[i][k]=f(dat[i][k-1],vs[k]); } } } T query(int l,int r){ if(l>=--r) return dat[0][l]; return f(dat[ht[l^r]][l],dat[ht[l^r]][r]); } }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; const int LIM = 1e9; using ll = long long; auto f=[&](int a,int b){return min((ll)a*b,(ll)LIM);}; DisjointSparseTable<int> st(f); st.build(as); auto h=[&](int a,int b){return a+b;}; SegmentTree<int> seg(h,0); seg.init(n); vector<int> zs; for(int i=0;i<n;i++) if(as[i]==0) zs.emplace_back(i); if(!zs.empty()) drop(0); using M = Mint<int>; M ans{1}; vector<M> bs(n+1,1); for(int i=0;i<n;i++) bs[i+1]=bs[i]*M(as[i]); for(int i=0;i<n;i++){ int l=i,r=n+1; // st.query(i, l) < LIM // st.query(i, r) >= LIM while(l+1<r){ int m=(l+r)>>1; if(st.query(i,m)<LIM) l=m; else r=m; } ans*=bs[i].pow(l-i).inv(); seg.update(i,l,1); // cout<<i<<' '<<l<<':'<<st.query(i,l)<<endl; // cout<<i<<' '<<r<<':'<<st.query(i,r)<<endl; } for(int i=0;i<n;i++) ans*=bs[i+1].pow(seg.get_val(i)); cout<<ans<<newl; return 0; }