結果

問題 No.749 クエリ全部盛り
ユーザー vwxyzvwxyz
提出日時 2024-04-09 09:15:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 564 ms / 3,000 ms
コード長 1,764 bytes
コンパイル時間 4,083 ms
コンパイル使用メモリ 290,360 KB
実行使用メモリ 116,716 KB
最終ジャッジ日時 2024-04-09 09:16:06
合計ジャッジ時間 8,004 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,948 KB
testcase_03 AC 2 ms
6,948 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 5 ms
6,944 KB
testcase_06 AC 4 ms
6,944 KB
testcase_07 AC 4 ms
6,948 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 36 ms
6,944 KB
testcase_11 AC 34 ms
6,944 KB
testcase_12 AC 32 ms
6,944 KB
testcase_13 AC 32 ms
6,944 KB
testcase_14 AC 32 ms
6,948 KB
testcase_15 AC 517 ms
116,716 KB
testcase_16 AC 530 ms
116,532 KB
testcase_17 AC 545 ms
116,472 KB
testcase_18 AC 523 ms
116,628 KB
testcase_19 AC 564 ms
116,540 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/lazysegtree>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const long long mod = 1000000007;


struct S {
    long long S;
    long long C;
    long long F;
};

struct F {
    long long a;
    long long p;
    long long c;
    long long f;
};

S op(S l, S r) {
	return S{(l.S+r.S)%mod, (l.C+r.C)%mod, (l.F+r.F)%mod};
}

S e() {
	return S{0ll, 0ll, 0ll};
}

F composition(F r, F l) {
	if (r.a!=-1ll){
		return F{r.a,r.p,r.c,r.f};
	}
	if (l.a!=-1ll){
		return F{(l.a*r.p+r.c)%mod,1ll,0ll,(l.f*r.p+r.f)%mod};
	}
    return F{-1ll, l.p*r.p%mod, (l.c*r.p+r.c)%mod, (l.f*r.p+r.f)%mod};
}

S mapping(F l, S r) {
    if (l.a!=-1ll){
        return S{((l.a*l.p%mod+l.c)*r.C%mod+l.f*r.F%mod)%mod, r.C, r.F};
    }
    return S{(r.S*l.p%mod+r.C*l.c%mod+l.f*r.F%mod)%mod, r.C, r.F};
}

F id() {
	return F{-1ll, 1ll, 0ll, 0ll};
}

vector<long long> fib;

int main() {
    int N, Q;
    cin >> N >> Q;

    fib.push_back(0ll);
    fib.push_back(1ll);
    for (int i = 2; i < N; ++i) {
        fib.push_back((fib[i - 1] + fib[i - 2]) % mod);
    }
    vector<S> a(N);
    for(int i=0;i<N;i++){
    	a[i]=S{0ll,1ll,fib[i]};
    }
    
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    for(int q=0;q<Q;q++){
    	int t,l,r;
    	long long k;
    	cin>>t>>l>>r>>k;
    	r+=1;
    	if(t==0){
	    	long long ans=k*(seg.prod(l,r).S)%mod;
	    	cout<<ans<<endl;
    	}
    	else if(t==1){
    		seg.apply(l,r,F({k,1ll,0ll,0ll}));
    	}
    	else if(t==2){
    		seg.apply(l,r,F({-1ll,1ll,k,0ll}));
    	}
    	else if(t==3){
    		seg.apply(l,r,F({-1ll,k,0ll,0ll}));
    	}
    	else if(t==4){
    		seg.apply(l,r,F({-1ll,1ll,0ll,k}));
    	}
    }
    return 0;
}
0