結果
問題 | No.749 クエリ全部盛り |
ユーザー | 夕叢霧香(ゆうむらきりか) |
提出日時 | 2018-10-07 00:49:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,786 ms / 3,000 ms |
コード長 | 3,059 bytes |
コンパイル時間 | 881 ms |
コンパイル使用メモリ | 76,668 KB |
最終ジャッジ日時 | 2025-01-06 14:24:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
36,748 KB |
testcase_01 | AC | 17 ms
35,316 KB |
testcase_02 | AC | 17 ms
35,368 KB |
testcase_03 | AC | 18 ms
36,908 KB |
testcase_04 | AC | 18 ms
37,068 KB |
testcase_05 | AC | 24 ms
35,616 KB |
testcase_06 | AC | 24 ms
35,464 KB |
testcase_07 | AC | 25 ms
36,532 KB |
testcase_08 | AC | 24 ms
35,332 KB |
testcase_09 | AC | 24 ms
35,720 KB |
testcase_10 | AC | 148 ms
35,576 KB |
testcase_11 | AC | 144 ms
36,476 KB |
testcase_12 | AC | 145 ms
35,472 KB |
testcase_13 | AC | 148 ms
36,572 KB |
testcase_14 | AC | 146 ms
36,720 KB |
testcase_15 | AC | 1,745 ms
43,004 KB |
testcase_16 | AC | 1,786 ms
42,936 KB |
testcase_17 | AC | 1,731 ms
42,796 KB |
testcase_18 | AC | 1,721 ms
42,852 KB |
testcase_19 | AC | 1,782 ms
42,880 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:142:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 142 | scanf("%d%d",&n,&q); | ~~~~~^~~~~~~~~~~~~~ main.cpp:145:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 145 | scanf("%d%d%d%d",&kind,&l,&r,&k); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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){if(k>=A)return;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);if(l>=r)return;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);int lb=(l+B-1)/B;int rb=r/B;if(lb>rb){upd_n_sx_plus_t(l,r,s,t);return;}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);if(l>=r)return;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);int lb=(l+B-1)/B;int rb=r/B;if(lb>rb){upd_n_fib(l,r,k);return;}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);if(l>=r)return 0;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);int lb=(l+B-1)/B;int rb=r/B;if(lb>rb){return calc_n(l,r);}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++;assert(kind>=0);assert(kind<=4);assert(l<r);assert(k>=0);assert(k<=1e9);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;}}}