結果
問題 | No.749 クエリ全部盛り |
ユーザー | 夕叢霧香(ゆうむらきりか) |
提出日時 | 2018-10-07 00:34:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,915 bytes |
コンパイル時間 | 753 ms |
コンパイル使用メモリ | 77,612 KB |
実行使用メモリ | 41,856 KB |
最終ジャッジ日時 | 2024-10-12 14:06:38 |
合計ジャッジ時間 | 9,172 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
34,944 KB |
testcase_01 | AC | 16 ms
34,944 KB |
testcase_02 | AC | 15 ms
34,816 KB |
testcase_03 | AC | 16 ms
34,816 KB |
testcase_04 | AC | 15 ms
34,944 KB |
testcase_05 | AC | 20 ms
34,944 KB |
testcase_06 | AC | 21 ms
34,944 KB |
testcase_07 | AC | 21 ms
34,944 KB |
testcase_08 | AC | 22 ms
34,944 KB |
testcase_09 | AC | 22 ms
34,816 KB |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
ソースコード
#include<algorithm> #include<iostream> #include<cstdio> #include<vector> #include<cassert> using namespace std; typedef long long lint; typedef vector<int>vi; typedef pair<int,int>pii; typedef pair<lint,lint>pll; #define rep(i,n)for(int i=0;i<(int)(n);++i) const lint mo=1e9+7; const int N=1000000; const int A=1000; const int B=N/A; lint a[N]; lint asum[A]; lint u[A],v[A]; lint tap[A]; pll phi[N]; pll phiacc[N+1]; pll add(pll a,pll b){ return pll((a.first+b.first)%mo,(a.second+b.second)%mo); } pll mul(pll a,pll b){ lint x=a.first*b.first+5*a.second*b.second; lint y=a.first*b.second+a.second*b.first; return pll(x%mo,y%mo); } void init(){ pll p((mo+1)/2,(mo+1)/2); pll c(1,0); rep(i,N){ phi[i]=c; phiacc[i+1]=add(phiacc[i],phi[i]); c=mul(c,p); } } void red(int k){ lint tmp=0; rep(i,B){ int idx=k*B+i; a[idx]=u[k]*a[idx]+v[k]+2*tap[k]*phi[idx].second; a[idx]%=mo; tmp=(tmp+a[idx])%mo; } u[k]=1; v[k]=0; tap[k]=0; asum[k]=tmp; } void upd_n_sx_plus_t(int l,int r,int s,int t){ assert(r<=l/B*B+B); red(l/B); lint tmp=asum[l/B]; for(int i=l;i<r;i++){ tmp+=mo-a[i]; a[i]=(a[i]*s+t)%mo; tmp+=a[i]; } asum[l/B]=tmp%mo; } void upd_sx_plus_t(int l,int r,int s,int t){ assert(l<=r); if((l+B-1)/B>=r/B){ upd_n_sx_plus_t(l,r,s,t); return; } int lb=(l+B-1)/B; int rb=r/B; upd_n_sx_plus_t(l,B*lb,s,t); upd_n_sx_plus_t(B*rb,r,s,t); for(int i=lb;i<rb;++i){ u[i]=u[i]*s%mo; v[i]=(v[i]*s+t)%mo; tap[i]=tap[i]*s%mo; } } void upd_n_fib(int l,int r,int k){ assert(r<=l/B*B+B); red(l/B); lint tmp=asum[l/B]; for(int i=l;i<r;i++){ tmp+=mo-a[i]; a[i]=(a[i]+2*phi[i].second*k)%mo; tmp+=a[i]; } asum[l/B]=tmp%mo; } void upd_fib(int l,int r,int k){ assert(l<=r); if((l+B-1)/B>=r/B){ upd_n_fib(l,r,k); return; } int lb=(l+B-1)/B; int rb=r/B; upd_n_fib(l,B*lb,k); upd_n_fib(B*rb,r,k); for(int i=lb;i<rb;++i){ tap[i]=(tap[i]+k)%mo; } } lint calc_n(int l,int r){ assert(r<=l/B*B+B); red(l/B); lint ans=0; for(int i=l;i<r;i++)ans=(ans+a[i])%mo; return ans; } lint calc(int l,int r){ assert(l<=r); if((l+B-1)/B>=r/B){ return calc_n(l,r); } int lb=(l+B-1)/B; int rb=r/B; lint ans=0; ans=calc_n(l,B*lb); ans+=calc_n(B*rb,r); for(int i=lb;i<rb;++i){ ans+=u[i]*asum[i]%mo; ans+=v[i]*B; ans+=2*tap[i]*(phiacc[i*B+B].second-phiacc[i*B].second+mo)%mo; ans%=mo; } return ans; } int main(){ init(); int n,q; scanf("%d%d",&n,&q); rep(_,q){ int kind,l,r,k; scanf("%d%d%d%d",&kind,&l,&r,&k); r++; switch(kind){ case 0: printf("%lld\n",k*calc(l,r)%mo); break; case 1: upd_sx_plus_t(l,r,0,k); break; case 2: upd_sx_plus_t(l,r,1,k); break; case 3: upd_sx_plus_t(l,r,k,0); break; case 4: upd_fib(l,r,k); break; } } }