#1193914 (C++14) No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ

• 問題: No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
• ユーザー: zelda_master
• 提出日時: 2026-10-21 01:19:30
• 言語: C++14 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: MLE
• 実行時間: -
• コード長: 3,677 bytes
• コンパイル時間: 479 ms
• コンパイル使用メモリ: 82,168 KB
• 実行使用メモリ: 531,016 KB
• 最終ジャッジ日時: 2026-10-21 01:20:49
• 合計ジャッジ時間: 49,432 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge6_0

ファイルパターン	結果
other	AC * 1 MLE * 9

ソースコード

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 150010;
const LL MOD = 1000000000000000009LL;

int q;
LL n, ans[6];

struct Node {
    int l, r, lz, cnt;
    bool cover;
    LL sum[6];
};

struct SegTree {
    Node seg[N * 50];
    int rt, idx;
    void PushUp(int u) {
        for (int i = 1; i <= 5; ++i) {
            seg[u].sum[i] = seg[seg[u].l].sum[i] + seg[seg[u].r].sum[i];
        }
    }
    void Apply(int u, LL len, int id, int cnt, bool cover) {
        for (int i = 1; i <= 5; ++i) {
            if (i == id) {
                if (cover) seg[u].sum[i] = len * cnt;
                else seg[u].sum[i] += len * cnt;
            } else {
                seg[u].sum[i] = 0;
            }
        }
        if (cover) {
            seg[u].lz = id;
            seg[u].cnt = cnt;
            seg[u].cover = true;
        } else if (!seg[u].lz) {
            seg[u].lz = id;
            seg[u].cnt = cnt;
            seg[u].cover = false;
        } else if (seg[u].lz == id) {
            seg[u].cnt += cnt;
        } else {
            seg[u].lz = id;
            seg[u].cnt = cnt;
            seg[u].cover = true;
        }
    }
    void PushDown(int u, LL ul, LL ur) {
        if (!seg[u].lz || ul == ur) return;
        if (!seg[u].l) seg[u].l = ++idx;
        if (!seg[u].r) seg[u].r = ++idx;
        LL mid = (ul + ur) >> 1;
        Apply(seg[u].l, mid - ul + 1, seg[u].lz, seg[u].cnt, seg[u].cover);
        Apply(seg[u].r, ur - mid, seg[u].lz, seg[u].cnt, seg[u].cover);
        seg[u].lz = 0;
        seg[u].cnt = 0;
        seg[u].cover = false;
    }
    void Modify(int &u, LL ul, LL ur, LL l, LL r, int id) {
        if (!u) u = ++idx;
        if (l <= ul && ur <= r) {
            Apply(u, ur - ul + 1, id, 1, false);
            return;
        }
        PushDown(u, ul, ur);
        LL mid = (ul + ur) >> 1;
        if (mid >= l) Modify(seg[u].l, ul, mid, l, r, id);
        if (mid + 1 <= r) Modify(seg[u].r, mid + 1, ur, l, r, id);
        PushUp(u);
    }
    Node Query(int u, LL ul, LL ur, LL l, LL r) {
        if (!u) return { 0, 0, 0 };
        if (l <= ul && ur <= r) return seg[u];
        PushDown(u, ul, ur);
        Node ret = { 0, 0, 0 };
        LL mid = (ul + ur) >> 1;
        if (mid >= l) {
            Node res = Query(seg[u].l, ul, mid, l, r);
            for (int i = 1; i <= 5; ++i) {
                ret.sum[i] += res.sum[i];
            }
        }
        if (mid + 1 <= r) {
            Node res = Query(seg[u].r, mid + 1, ur, l, r);
            for (int i = 1; i <= 5; ++i) {
                ret.sum[i] += res.sum[i];
            }
        }
        return ret;
    }
};
SegTree sgt;

int main() {
    // freopen("color.in", "r", stdin);
    // freopen("color.out", "w", stdout);

    scanf("%lld%d", &n, &q);
    while (q--) {
        int op;
        LL l, r;
        scanf("%d%lld%lld", &op, &l, &r);
        if (op == 0) {
            Node res = sgt.Query(sgt.rt, 0, n - 1, l, r);
            LL ma = 0;
            int ma_idx = -1;
            for (int i = 1; i <= 5; ++i) {
                if (ma < res.sum[i]) {
                    ma = res.sum[i];
                    ma_idx = i;
                } else if (ma == res.sum[i]) {
                    ma_idx = -1;
                }
            }
            if (ma > 0 && ma_idx != -1) {
                ans[ma_idx] = (ans[ma_idx] + ma % MOD) % MOD;
            }
        } else {
            sgt.Modify(sgt.rt, 0, n - 1, l, r, op);
        }
    }

    for (int i = 1; i <= 5; ++i) {
        LL result = (ans[i] + sgt.seg[sgt.rt].sum[i] % MOD) % MOD;
        printf("%lld%c", result, " \n"[i == 5]);
    }

    return 0;
}