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

• 問題: No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
• ユーザー: vjudge1
• 提出日時: 2026-10-17 08:49:56
• 言語: C++14 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 944 ms / 10,000 ms
• コード長: 3,586 bytes
• コンパイル時間: 1,264 ms
• コンパイル使用メモリ: 188,040 KB
• 実行使用メモリ: 64,300 KB
• 最終ジャッジ日時: 2026-10-17 08:50:19
• 合計ジャッジ時間: 11,488 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge5_0

ファイルパターン	結果
other	AC * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1 << 19;
ll n, q;
int op[150005];
ll lo[150005], ro[150005];
ll v[M + 5];
int vn;
ll va[5][M * 2];
ll to[5][M * 2];
char cl[5][M * 2];
ll bs[5];
ll mo = 1000000000000000009LL;

void dc(int id, int x) {
    if (x < 2 * M) {
        cl[id][x] = 1;
        va[id][x] = 0;
        to[id][x] = 0;
    }
}

ll gv(int id, int x, int y, int l, int r, int k) {
    if (r <= x || y <= l) return 0;
    if (cl[id][k]) return 0;
    if (x <= l && r <= y) return to[id][k];
    x = max(x, l);
    y = min(y, r);
    return va[id][k] * (v[y] - v[x]) + gv(id, x, y, l, (l + r) / 2, 2 * k) + gv(id, x, y, (l + r) / 2, r, 2 * k + 1);
}

void cr(int id, int x, int y, int l, int r, int k) {
    if (r <= x || y <= l) return;
    if (cl[id][k]) return;
    if (x <= l && r <= y) {
        cl[id][k] = 1;
        va[id][k] = 0;
        to[id][k] = 0;
    } else {
        if (cl[id][2 * k]) {
            cl[id][2 * k] = 0;
            va[id][2 * k] = 0;
            to[id][2 * k] = 0;
            dc(id, 4 * k);
            dc(id, 4 * k + 1);
        }
        if (cl[id][2 * k + 1]) {
            cl[id][2 * k + 1] = 0;
            va[id][2 * k + 1] = 0;
            to[id][2 * k + 1] = 0;
            dc(id, 4 * k + 2);
            dc(id, 4 * k + 3);
        }
        va[id][2 * k] += va[id][k];
        to[id][2 * k] += va[id][k] * (v[(l + r) / 2] - v[l]);
        va[id][2 * k + 1] += va[id][k];
        to[id][2 * k + 1] += va[id][k] * (v[r] - v[(l + r) / 2]);
        va[id][k] = 0;
        cr(id, x, y, l, (l + r) / 2, 2 * k);
        cr(id, x, y, (l + r) / 2, r, 2 * k + 1);
        to[id][k] = to[id][2 * k] + to[id][2 * k + 1];
    }
}

void ic(int id, int x, int y, int l, int r, int k) {
    if (r <= x || y <= l) return;
    if (cl[id][k]) {
        dc(id, 2 * k);
        dc(id, 2 * k + 1);
        cl[id][k] = 0;
        va[id][k] = 0;
        to[id][k] = 0;
    }
    if (x <= l && r <= y) {
        va[id][k]++;
        to[id][k] += v[r] - v[l];
    } else {
        ic(id, x, y, l, (l + r) / 2, 2 * k);
        ic(id, x, y, (l + r) / 2, r, 2 * k + 1);
        to[id][k] = va[id][k] * (v[r] - v[l]) + to[id][2 * k] + to[id][2 * k + 1];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    vn = 0;
    v[vn++] = 0;
    v[vn++] = n + 3;
    for (int i = 0; i < q; i++) {
        cin >> op[i] >> lo[i] >> ro[i];
        lo[i]++;
        ro[i]++;
        v[vn++] = lo[i];
        v[vn++] = ro[i] + 1;
    }
    sort(v, v + vn);
    vn = unique(v, v + vn) - v;
    while (vn < M + 5) v[vn++] = v[vn - 1];
    for (int i = 0; i < q; i++) {
        int p1 = lower_bound(v, v + vn, lo[i]) - v;
        int p2 = lower_bound(v, v + vn, ro[i] + 1) - v;
        if (op[i] == 0) {
            ll bo[5] = {0};
            int bi = 0;
            for (int j = 0; j < 5; j++) {
                bo[j] = gv(j, p1, p2, 0, M, 1);
                if (bo[j] > bo[bi]) bi = j;
            }
            for (int j = 0; j < 5; j++) {
                if (bi >= 0 && j != bi && bo[j] == bo[bi]) bi = -1;
            }
            if (bi != -1) {
                bs[bi] = (bs[bi] + bo[bi]) % mo;
            }
        } else {
            for (int j = 0; j < 5; j++) {
                if (op[i] == j + 1) {
                    ic(j, p1, p2, 0, M, 1);
                } else {
                    cr(j, p1, p2, 0, M, 1);
                }
            }
        }
    }
    for (int i = 0; i < 5; i++) {
        cout << ((bs[i] + gv(i, 0, M, 0, M, 1)) % mo) << " \n"[i == 4];
    }
    return 0;
}