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

• 問題: No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
• ユーザー: vjudge1
• 提出日時: 2026-10-17 08:46:03
• 言語: C++14 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,565 bytes
• コンパイル時間: 1,202 ms
• コンパイル使用メモリ: 186,408 KB
• 実行使用メモリ: 14,636 KB
• 最終ジャッジ日時: 2026-10-17 08:46:12
• 合計ジャッジ時間: 4,325 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX = 300005;
const ll MOD = 1000000000000000009LL;

ll a[MAX], op[3][150005];
ll len[4 * MAX], s[5][4 * MAX], ans[5];
int cov[4 * MAX];
int n, q, m;

int bnd(ll *arr, int n, ll val) {
    int l = 0, r = n - 1, res = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] >= val) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

void pdn(int u) {
    if (cov[u] != -1) {
        int c = cov[u];
        cov[u * 2] = cov[u * 2 + 1] = c;
        for (int i = 0; i < 5; i++) s[i][u * 2] = s[i][u * 2 + 1] = 0;
        s[c][u * 2] = len[u * 2];
        s[c][u * 2 + 1] = len[u * 2 + 1];
    }
}

void upd(int u, int l, int r, int L, int R, int c) {
    if (L <= l && r <= R) {
        if (cov[u] == c) {
            s[c][u] += len[u];
        } else if (cov[u] != -1) {
            s[cov[u]][u] -= len[u];
            s[c][u] += len[u];
            cov[u] = c;
        } else {
            pdn(u);
            int mid = (l + r) / 2;
            upd(u * 2, l, mid, L, R, c);
            upd(u * 2 + 1, mid + 1, r, L, R, c);
            for (int i = 0; i < 5; i++) s[i][u] = s[i][u * 2] + s[i][u * 2 + 1];
            if (cov[u * 2] == cov[u * 2 + 1]) cov[u] = cov[u * 2];
            else cov[u] = -1;
        }
        return;
    }
    pdn(u);
    int mid = (l + r) / 2;
    if (L <= mid) upd(u * 2, l, mid, L, R, c);
    if (R > mid) upd(u * 2 + 1, mid + 1, r, L, R, c);
    for (int i = 0; i < 5; i++) s[i][u] = s[i][u * 2] + s[i][u * 2 + 1];
    if (cov[u * 2] == cov[u * 2 + 1]) cov[u] = cov[u * 2];
    else cov[u] = -1;
}

void qry(int u, int l, int r, int L, int R, ll *res) {
    if (L <= l && r <= R) {
        for (int i = 0; i < 5; i++) res[i] += s[i][u];
        return;
    }
    pdn(u);
    int mid = (l + r) / 2;
    if (L <= mid) qry(u * 2, l, mid, L, R, res);
    if (R > mid) qry(u * 2 + 1, mid + 1, r, L, R, res);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> q;
    int cnt = 0;
    a[cnt++] = 0;
    a[cnt++] = n;
    
    for (int i = 0; i < q; i++) {
        cin >> op[0][i] >> op[1][i] >> op[2][i];
        a[cnt++] = op[1][i];
        a[cnt++] = op[2][i] + 1;
    }
    
    sort(a, a + cnt);
    m = 1;
    for (int i = 1; i < cnt; i++) {
        if (a[i] != a[i - 1]) a[m++] = a[i];
    }
    
    for (int i = 1; i < m; i++) {
        len[i] = a[i] - a[i - 1];
    }
    
    memset(cov, -1, sizeof(cov));
    
    for (int i = 0; i < q; i++) {
        int x = op[0][i];
        ll l = op[1][i], r = op[2][i];
        int L = bnd(a, m, l) + 1;
        int R = bnd(a, m, r + 1);
        
        if (x == 0) {
            ll res[5] = {0};
            qry(1, 1, m - 1, L, R, res);
            ll mx = -1;
            int cnt_mx = 0;
            for (int j = 0; j < 5; j++) {
                if (res[j] > mx) {
                    mx = res[j];
                    cnt_mx = 1;
                } else if (res[j] == mx) {
                    cnt_mx++;
                }
            }
            if (cnt_mx == 1) {
                for (int j = 0; j < 5; j++) {
                    if (res[j] == mx) {
                        ans[j] = (ans[j] + mx) % MOD;
                        break;
                    }
                }
            }
        } else {
            upd(1, 1, m - 1, L, R, x - 1);
        }
    }
    
    cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << "\n";
    return 0;
}