結果

問題 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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0