結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー WutongDeath
提出日時 2026-10-21 03:08:10
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 318 ms / 10,000 ms
+ 942µs
コード長 3,942 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,101 ms
コンパイル使用メモリ 182,468 KB
実行使用メモリ 91,824 KB
最終ジャッジ日時 2026-10-21 03:08:28
合計ジャッジ時間 10,240 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 150010, M = 300010;
const LL MOD = 1000000000000000009LL;

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

struct Query {
    int x;
    LL l, r;
};

struct SegTree {
    Node seg[M << 2];
    void Build(int u, int l, int r, LL a[]) {
        seg[u].l = l, seg[u].r = r;
        seg[u].len = a[r + 1] - a[l];
        if (l == r) return;
        int mid = l + r >> 1;
        Build(u << 1, l, mid, a);
        Build(u << 1 | 1, mid + 1, r, a);
    }
    void PushUp(int u) {
        for (int i = 1; i <= 5; ++i) {
            seg[u].sum[i] = seg[u << 1].sum[i] + seg[u << 1 | 1].sum[i];
        }
    }
    void ApplyAdd(int u, int id, int cnt, bool cover) {
        for (int i = 1; i <= 5; ++i) {
            if (i == id) {
                if (cover) seg[u].sum[i] = seg[u].len * cnt;
                else seg[u].sum[i] += seg[u].len * cnt;
            } else {
                seg[u].sum[i] = 0;
            }
        }
        if (cover) {
            seg[u].col = id;
            seg[u].cnt = cnt;
            seg[u].cover = true;
        } else if (!seg[u].col) {
            seg[u].col = id;
            seg[u].cnt = cnt;
            seg[u].cover = false;
        } else if (seg[u].col == id) {
            seg[u].cnt += cnt;
        } else {
            seg[u].col = id;
            seg[u].cnt = cnt;
            seg[u].cover = true;
        }
    }
    void PushDown(int u) {
        if (!seg[u].col || seg[u].l == seg[u].r) return;
        ApplyAdd(u << 1, seg[u].col, seg[u].cnt, seg[u].cover);
        ApplyAdd(u << 1 | 1, seg[u].col, seg[u].cnt, seg[u].cover);
        seg[u].col = seg[u].cnt = 0;
        seg[u].cover = false;
    }
    void Modify(int u, int l, int r, int id) {
        if (l <= seg[u].l && seg[u].r <= r) {
            ApplyAdd(u, id, 1, false);
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (l <= mid) Modify(u << 1, l, r, id);
        if (mid < r) Modify(u << 1 | 1, l, r, id);
        PushUp(u);
    }
    Node Query(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u];
        PushDown(u);
        Node ret = {};
        int mid = seg[u].l + seg[u].r >> 1;
        if (l <= mid) {
            Node t = Query(u << 1, l, r);
            for (int i = 1; i <= 5; ++i) ret.sum[i] += t.sum[i];
        }
        if (mid < r) {
            Node t = Query(u << 1 | 1, l, r);
            for (int i = 1; i <= 5; ++i) ret.sum[i] += t.sum[i];
        }
        return ret;
    }
};
SegTree sgt;

int q, cnt;
LL n, a[M], ans[6];
Query op[N];

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

    scanf("%lld%d", &n, &q);
    a[++cnt] = 0LL, a[++cnt] = n;
    for (int i = 1; i <= q; ++i) {
        scanf("%d%lld%lld", &op[i].x, &op[i].l, &op[i].r);
        ++op[i].r;
        a[++cnt] = op[i].l, a[++cnt] = op[i].r;
    }

    sort(a + 1, a + cnt + 1);
    cnt = unique(a + 1, a + cnt + 1) - a - 1;
    sgt.Build(1, 1, cnt - 1, a);

    for (int i = 1; i <= q; ++i) {
        int l = lower_bound(a + 1, a + cnt + 1, op[i].l) - a;
        int r = lower_bound(a + 1, a + cnt + 1, op[i].r) - a - 1;
        if (op[i].x == 0) {
            Node t = sgt.Query(1, l, r);
            LL mx = 0LL;
            int id = -1;
            for (int j = 1; j <= 5; ++j) {
                if (mx < t.sum[j]) {
                    mx = t.sum[j], id = j;
                } else if (mx == t.sum[j]) {
                    id = -1;
                }
            }
            if (id != -1) (ans[id] += mx % MOD) %= MOD;
        } else {
            sgt.Modify(1, l, r, op[i].x);
        }
    }

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

    return 0;
}
0