結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー vwxyzvwxyz
提出日時 2024-04-11 12:53:51
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5,083 ms / 10,000 ms
コード長 3,279 bytes
コンパイル時間 4,883 ms
コンパイル使用メモリ 277,292 KB
実行使用メモリ 182,408 KB
最終ジャッジ日時 2024-10-02 21:33:45
合計ジャッジ時間 54,437 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5,038 ms
182,284 KB
testcase_01 AC 5,004 ms
182,280 KB
testcase_02 AC 5,083 ms
182,152 KB
testcase_03 AC 4,667 ms
182,408 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 4,773 ms
182,280 KB
testcase_06 AC 5,025 ms
182,152 KB
testcase_07 AC 4,768 ms
182,244 KB
testcase_08 AC 4,767 ms
182,152 KB
testcase_09 AC 5,028 ms
182,152 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=1000000000000000009ll;
using S =vector<long long>;

using F =vector<long long>;

S op(S l, S r) {
    S retu(6);
    for(int i=0;i<6;i++){
        retu[i]=(l[i]+r[i])%mod;
    }
    return retu;
}

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

F composition(F l, F r) {
    if(l[5]){
        F retu(6);
        for(int i=0;i<6;i++){
            retu[i]=l[i];
        }
        return retu;
    }
    for(int i=0;i<5;i++){
        if(l[i]){
            F retu(6,0ll);
            retu[i]=(l[i]+r[i])%mod;
            if(r[5]){
                retu[5]=1ll;
            }
            for(int j=0;j<5;j++){
                if(i==j){
                    continue;
                }
                if(r[j]){
                    retu[5]=1ll;
                }
            }
            return retu;
        }
    }
    F retu(6);
    for(int i=0;i<6;i++){
        retu[i]=r[i];
    }
    return retu;
}

S mapping(F l, S r) {
    S retu(6,0ll);
    for(int i=0;i<5;i++){
        if(l[i]){
            long long a=l[i];
            long long c=r[5];
            retu[5]=c;
            if(l[5]){
                retu[i]=a*c%mod;
            }
            else{
                retu[i]=(r[i]+a*c%mod)%mod;
            }
            return retu;
        }
    }
    for(int i=0;i<6;i++){
        retu[i]=r[i];
    }
    return retu;
}

F id() {
	return F(6,0ll);
}

int main() {
    long long N;
    cin >> N;
    vector<long long> ans(5,0ll);
    int Q;
    cin >> Q;
    vector<long long> X(Q),L(Q),R(Q),bound;
    bound={0,N};
    for(int q=0;q<Q;q++){
        cin>>X[q]>>L[q]>>R[q];
        R[q]+=1;
        bound.push_back(L[q]);
        bound.push_back(R[q]);
    }
    sort(bound.begin(), bound.end());
    bound.erase(unique(bound.begin(), bound.end()), bound.end());
    unordered_map<long long,int> comp;
    int le=bound.size()-1;
    for (int i = 0; i < le+1; ++i) {
        comp[bound[i]] = i;
    }
    for(int q=0;q<Q;q++){
        L[q]=comp[L[q]];
        R[q]=comp[R[q]];
    }
    vector<S> a(le);
    for(int i=0;i<le;i++){
        a[i]=S(6,0ll);
        a[i][5]=bound[i+1]-bound[i];
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    for(int q=0;q<Q;q++){
        if (X[q]){
            S vec(6,0ll);
            vec[X[q]-1]=1ll;
            seg.apply(L[q],R[q],vec);
        }
        else{
            S vec=seg.prod(L[q],R[q]);
            long long m=-1;
            vector<int> idx;
            for(int i=0;i<5;i++){
                if (m<vec[i]){
                    m=vec[i];
                    idx={i};
                }
                else if(m==vec[i]){
                    idx.push_back(i);
                }
            }
            if(idx.size()>=2){
                continue;
            }
            assert(idx.size());
            ans[idx[0]]+=m;
            ans[idx[0]]%=mod;
        }
        S vec=seg.all_prod();
    }
    S vec=seg.all_prod();
    for(int i=0;i<5;i++){
        ans[i]+=vec[i];
        ans[i]%=mod;
    }
    for(int i=0;i<5;i++){
        if(i){
            cout<<" ";
        }
        cout<<ans[i];
    }
    cout<<endl;
    return 0;
}
0