#292864 (C++17) No.749 クエリ全部盛り

提出ソース

結果

問題	No.749 クエリ全部盛り
ユーザー	beet
提出日時	2018-10-19 21:59:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,975 bytes
コンパイル時間	2,730 ms
コンパイル使用メモリ	233,108 KB
実行使用メモリ	97,916 KB
最終ジャッジ日時	2024-11-18 20:35:09
合計ジャッジ時間	7,582 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
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;}


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(int n_,F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){init(n_);}
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(int k){
    return g(dat[k],laz[k]);
  }
  inline void eval(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]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void recalc(int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(int a,int b,E x){
    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);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(int k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  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-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  static vector<Mint> fact,finv,invs;
  
  static void init(int n){
    if(n+1<=(signed)fact.size()) return;
    fact.assign(n+1,1);
    finv.assign(n+1,1);
    invs.assign(n+1,1);
    
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*Mint(i);
    finv[n]=Mint(1)/fact[n];
    for(int i=n;i>=1;i--) finv[i-1]=finv[i]*Mint(i);
    for(int i=1;i<=n;i++) invs[i]=finv[i]*fact[i-1];
  }

  static Mint comb(long long n,int k){
    Mint res(1);
    for(int i=0;i<k;i++){
      res*=Mint(n-i);
      res/=Mint(i+1);
    }
    return res;
  }
  
  static Mint C(int n,int k){
    if(n<k||k<0) return Mint(0);
    init(n);
    return fact[n]*finv[n-k]*finv[k];
  }

  static Mint P(int n,int k){
    if(n<k||k<0) return Mint(0);
    init(n);
    return fact[n]*finv[n-k];
  }
  
  static Mint H(int n,int k){
    if(n<0||k<0) return Mint(0);
    if(!n&&!k) return Mint(1);
    init(n+k-1);
    return C(n+k-1,n);
  }

  static Mint S(int n,int k){
    Mint res;
    init(k);
    for(int i=1;i<=k;i++){
      Mint tmp=C(k,i)*Mint(i).pow(n);
      if((k-i)&1) res-=tmp;
      else res+=tmp;
    }    
    return res*=finv[k];
  }

  static vector<vector<Mint> > D(int n,int m){
    vector<vector<Mint> > dp(n+1,vector<Mint>(m+1,0));
    dp[0][0]=Mint(1);
    for(int i=0;i<=n;i++){
      for(int j=1;j<=m;j++){
	if(i-j>=0) dp[i][j]=dp[i][j-1]+dp[i-j][j];
	else dp[i][j]=dp[i][j-1];
      }
    }
    return dp;
  }

  static Mint B(int n,int k){
    Mint res;
    for(int j=1;j<=k;j++) res+=S(n,j);
    return res;
  }

  static Mint montmort(int n){
    Mint res;
    init(n);
    for(int k=2;k<=n;k++){
      if(k&1) res-=finv[k];
      else res+=finv[k];
    }
    return res*=fact[n];
  }

  static Mint LagrangePolynomial(vector<Mint> &y,Mint t){
    int n=y.size()-1;
    init(n+1);
    Mint num(1);
    for(int i=0;i<=n;i++) num*=t-Mint(i);
    Mint res;
    for(int i=0;i<=n;i++){
      Mint tmp=y[i]*num/(t-Mint(i))*finv[i]*finv[n-i];
      if((n-i)&1) res-=tmp;
      else res+=tmp;
    }
    return res;
  }
};
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::fact = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::finv = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::invs = vector<Mint<T, MOD> >();

//INSERT ABOVE HERE
signed main(){
  int n,q;
  scanf("%d %d",&n,&q);
  vector<int> t(q),l(q),r(q),k(q);
  for(int i=0;i<q;i++)
    scanf("%d %d %d %d",&t[i],&l[i],&r[i],&k[i]);

  using M = Mint<int>;

  using T = tuple<M, M, M>;
  using E = tuple<bool, M, M, M, M>;

  auto f=[](T a,T b){
	   M as,ac,af;
	   M bs,bc,bf;
	   tie(as,ac,af)=a;
	   tie(bs,bc,bf)=b;
	   return T(as+bs,ac+bc,af+bf);
	 };

  auto g=[](T a,E b){
	   M as,ac,af;
	   M bu,ba,bm,bf;
	   bool upd;
	   tie(as,ac,af)=a;
	   tie(upd,bu,ba,bm,bf)=b;
	   if(upd) as=bu*ac;
	   as*=bm;
	   as+=ba*ac;
	   as+=bf*af;
	   //cout<<as.v<<" vvv "<<bm.v<<endl;
	   //cout<<ba.v<<" --- "<<ac.v<<endl;
	   //cout<<bf.v<<" ^^^ "<<af.v<<endl;
	   return T(as,ac,af);
	 };

  auto h=[](E a,E b){
	   M au,aa,am,af;
	   M bu,ba,bm,bf;
	   bool ua,ub;
	   tie(ua,au,aa,am,af)=a;
	   tie(ub,bu,ba,bm,bf)=b;
	   if(ub) return b;
	   au*=bm;
	   aa*=bm;	   
	   am*=bm;
	   af*=bm;
	   
	   aa+=ba;
	   af+=bf;
	   return E(ua,au,aa,am,af);
	 };

  T ti(M(0),M(0),M(0));
  E ei(false,M(0),M(0),M(1),M(0));
  SegmentTree<T, E> seg(n,f,g,h,ti,ei);

  vector<M> fib(n);
  vector<T> vt(n);
  for(int i=0;i<n;i++){
    if(i==0) fib[i]=M(0);
    if(i==1) fib[i]=M(1);
    if(i>=2) fib[i]=fib[i-1]+fib[i-2];
    vt[i]=T(M(0),M(1),fib[i]);
  }
  seg.build(n,vt);
  
  for(int i=0;i<q;i++){
    r[i]++;
    M v(k[i]);
    if(t[i]==0){
      T res=seg.query(l[i],r[i]);
      printf("%d\n",(v*get<0>(res)).v);
    }
    if(t[i]==1){
      E x(true,v,M(0),M(1),M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==2){
      E x(false,M(0),v,M(1),M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==3){
      E x(false,M(0),M(0),v,M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==4){
      E x(false,M(0),M(0),M(1),v);
      seg.update(l[i],r[i],x);
    }
    continue;
    for(int j=0;j<n;j++) cout<<get<0>(seg.query(j,j+1)).v<<" ";
    cout<<endl;
  }
  
  return 0;
}

yukicoder

結果

テストケース

ソースコード