結果

問題 No.749 クエリ全部盛り
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-10-07 12:19:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,273 ms / 3,000 ms
コード長 3,229 bytes
コンパイル時間 786 ms
コンパイル使用メモリ 79,120 KB
実行使用メモリ 42,752 KB
最終ジャッジ日時 2024-10-12 14:12:46
合計ジャッジ時間 8,901 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
34,816 KB
testcase_01 AC 17 ms
34,688 KB
testcase_02 AC 17 ms
34,816 KB
testcase_03 AC 17 ms
34,816 KB
testcase_04 AC 18 ms
34,688 KB
testcase_05 AC 21 ms
34,688 KB
testcase_06 AC 21 ms
34,816 KB
testcase_07 AC 21 ms
34,688 KB
testcase_08 AC 21 ms
34,688 KB
testcase_09 AC 22 ms
34,688 KB
testcase_10 AC 100 ms
34,944 KB
testcase_11 AC 101 ms
34,816 KB
testcase_12 AC 100 ms
34,944 KB
testcase_13 AC 100 ms
34,944 KB
testcase_14 AC 99 ms
34,816 KB
testcase_15 AC 1,273 ms
42,624 KB
testcase_16 AC 1,262 ms
42,752 KB
testcase_17 AC 1,252 ms
42,624 KB
testcase_18 AC 1,262 ms
42,688 KB
testcase_19 AC 1,254 ms
42,624 KB
権限があれば一括ダウンロードができます

ソースコード

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];
lint madd(lint a,lint b){
  lint c=a+b;
  return c>=mo?c-mo:c;
}
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=madd(tmp,a[idx]);
  }
  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=madd(tmp,mo-a[i]);
    a[i]=(a[i]*s+t)%mo;
    tmp=madd(tmp,a[i]);
  }
  asum[l/B]=tmp;
}
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=madd(tmp,mo-a[i]);
    a[i]=(a[i]+2*phi[i].second*k)%mo;
    tmp=madd(tmp,a[i]);
  }
  asum[l/B]=tmp;
}
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]=madd(tap[i],k);
  }
}

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=madd(ans,a[i]);
  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);
  assert(n<=1e6);
  assert(q<=1e5);
  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(l>=0);
    assert(r<=n);
    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;
    }
  }
}
0