結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー vwxyzvwxyz
提出日時 2024-04-11 07:31:16
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,753 bytes
コンパイル時間 3,527 ms
コンパイル使用メモリ 273,048 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-02 21:21:12
合計ジャッジ時間 4,465 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 2 ms
5,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
using namespace atcoder;

const long long mod=1000000000000000009;
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) {
    for(int i=0;i<5;i++){
        if(l[i]){
            F retu(5,0ll);
            retu[i]=(l[i]+r[i])%mod;
            return retu;
        }
    }
    F retu(5);
    for(int i=0;i<5;i++){
        retu[i]=r[i];
    }
    return retu;
}

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

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

int main() {
    int N;
    cin >> N;
    vector<long long> ans(5,0ll);
    int Q;
    cin >> Q;
    vector<long long> X(Q),bound;
    vector<long long> L(Q),R(Q);
    bound={0ll,1000000000000000ll};
    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]);
            vec.pop_back();
            long long m=*max_element(begin(vec), end(vec));
            int c=0;
            for(int i=0;i<5;i++){
                if(vec[i]==m){
                    c+=1;
                }
            }
            if(c>=2){
                continue;
            }
            for(int i=0;i<5;i++){
                if(vec[i]==m){
                    ans[i]+=m;
                    ans[i]%=mod;
                }
            }
        }
    }
    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