結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー pekempeypekempey
提出日時 2016-10-29 11:42:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 435 ms / 10,000 ms
コード長 3,033 bytes
コンパイル時間 1,350 ms
コンパイル使用メモリ 148,660 KB
実行使用メモリ 62,780 KB
最終ジャッジ日時 2023-08-16 06:35:48
合計ジャッジ時間 6,789 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 435 ms
62,624 KB
testcase_01 AC 434 ms
62,624 KB
testcase_02 AC 414 ms
62,624 KB
testcase_03 AC 354 ms
62,756 KB
testcase_04 AC 15 ms
38,344 KB
testcase_05 AC 421 ms
62,712 KB
testcase_06 AC 423 ms
62,684 KB
testcase_07 AC 418 ms
62,532 KB
testcase_08 AC 416 ms
62,780 KB
testcase_09 AC 418 ms
62,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

struct node {
    int64_t sum[5];
    int64_t w;
    int fill;
    int thick;
    bool reset;
};

const int64_t mod = int64_t(1e18) + 9;
const int H = 19;
const int N = 1 << H;
const int Q = 150000;

int q;
int64_t n, X[Q], L[Q], R[Q], dict[Q * 2], sum[5], result[5];
node ns[N * 2];

void set_lazy(int k, int c, int thick, bool reset) {
    if (ns[k].thick > 0 && ns[k].fill != c) reset = true;
    int64_t s = ns[k].sum[c];
    memset(ns[k].sum, 0, sizeof(ns[k].sum));
    if (reset) {
        ns[k].thick = 0;
        ns[k].reset = true;
        s = 0;
    }
    ns[k].thick += thick;
    ns[k].fill = c;
    ns[k].sum[c] = thick * ns[k].w + s;
}

void push(int k) {
    if (ns[k].thick == 0) return;
    set_lazy(k * 2 + 0, ns[k].fill, ns[k].thick, ns[k].reset);
    set_lazy(k * 2 + 1, ns[k].fill, ns[k].thick, ns[k].reset);
    ns[k].fill = -1;
    ns[k].thick = 0;
    ns[k].reset = false;
}

void fix(int k) {
    for (int i = 0; i < 5; i++) {
        ns[k].sum[i] = ns[k * 2].sum[i] + ns[k * 2 + 1].sum[i];
    }
}

void add(int k) {
    for (int i = 0; i < 5; i++) result[i] += ns[k].sum[i];
}

void push_sup(int l, int r) {
    for (int i = H; i >= 1; i--) {
        push(l >> i);
        push(r >> i);
    }
}

void update(int l, int r, int c) {
    int ll = -1, rr = -1;
    l += N;
    r += N;
    push_sup(l, r - 1);
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ll = std::max(ll, l), set_lazy(l++, c, 1, false);
        if (r & 1) set_lazy(--r, c, 1, false), rr = std::max(rr, r);
    }
    for (; ll > 1; ll >>= 1) fix(ll >> 1);
    for (; rr > 1; rr >>= 1) fix(rr >> 1);
}


void query(int l, int r) {
    l += N;
    r += N;
    push_sup(l, r - 1);
    memset(result, 0, sizeof(result));
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) add(l++);
        if (r & 1) add(--r);
    }
}

int64_t in() {
    int64_t t;
    scanf("%lld", &t);
    return t;
}

int main() {
    n = in(), q = in();
    for (int i = 0; i < q; i++) {
        X[i] = in() - 1, L[i] = in(), R[i] = in() + 1;
        dict[i * 2 + 0] = L[i];
        dict[i * 2 + 1] = R[i];
    }
    std::sort(dict, dict + q * 2);
    int m = std::unique(dict, dict + q * 2) - dict;
    for (int i = 0; i < m - 1; i++) ns[i + N].w = dict[i + 1] - dict[i];
    for (int i = N - 1; i >= 1; i--) ns[i].w = ns[i * 2].w + ns[i * 2 + 1].w;
    for (int i = 0; i < q; i++) {
        L[i] = std::lower_bound(dict, dict + m, L[i]) - dict;
        R[i] = std::lower_bound(dict, dict + m, R[i]) - dict;
        if (X[i] == -1) {
            query(L[i], R[i]);
            int id = std::max_element(result, result + 5) - result;
            for (int j = 0; j < 5; j++) {
                if (j != id && result[j] == result[id]) {
                    id = -1;
                    break;
                }
            }
            if (id >= 0) (sum[id] += result[id]) %= mod;
        } else {
            update(L[i], R[i], X[i]);
        }
    }
    for (int i = 0; i < 5; i++) printf("%lld ", (ns[1].sum[i] + sum[i]) % mod);
}
0