結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー mkreemmkreem
提出日時 2024-03-09 11:15:03
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,915 bytes
コンパイル時間 1,152 ms
コンパイル使用メモリ 123,352 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-09-29 21:13:01
合計ジャッジ時間 3,394 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 8 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 4 ms
6,816 KB
testcase_09 AC 59 ms
6,816 KB
testcase_10 AC 76 ms
6,816 KB
testcase_11 AC 36 ms
6,816 KB
testcase_12 AC 59 ms
6,816 KB
testcase_13 AC 11 ms
6,820 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 110 ms
7,680 KB
testcase_17 AC 119 ms
7,680 KB
testcase_18 AC 89 ms
7,592 KB
testcase_19 AC 71 ms
7,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <iostream>

class LazySegTree {
public:
    static std::tuple<int, int, int> X_unit;  // (0, 0, 0) 無色、色1、色2
    static int A_unit;

    static std::tuple<int, int, int> X_f(std::tuple<int, int, int> x, std::tuple<int, int, int> y) {
        int a, b, c, d, e, f;
        std::tie(a, b, c) = x;
        std::tie(d, e, f) = y;
        return std::make_tuple(a + d, b + e, c + f);
    }

    static int A_f(int x, int y) {
        if (y == 0) return x;
        return y;
    }

    static std::tuple<int, int, int> operate(std::tuple<int, int, int> x, int y) {
        if (y == 0) return x;
        int s = std::get<0>(x) + std::get<1>(x) + std::get<2>(x);
        if (y == 1) return std::make_tuple(0, s, 0);
        else return std::make_tuple(0, 0, s);
    }

    LazySegTree(int N) : N(N), X(N + N, X_unit), A(N + N, A_unit) {}

    void build(std::vector<std::tuple<int, int, int>>& seq) {
        for (int i = 0; i < seq.size(); ++i) {
            X[i + N] = seq[i];
        }
        for (int i = N - 1; i > 0; --i) {
            X[i] = X_f(X[i << 1], X[i << 1 | 1]);
        }
    }

    std::tuple<int, int, int> _eval_at(int i) {
        return operate(X[i], A[i]);
    }

    void _propagate_at(int i) {
        X[i] = _eval_at(i);
        A[i << 1] = A_f(A[i << 1], A[i]);
        A[i << 1 | 1] = A_f(A[i << 1 | 1], A[i]);
        A[i] = A_unit;
    }

    void _propagate_above(int i) {
        int H = std::log2(i) + 1;
        for (int h = H; h > 0; --h) {
            _propagate_at(i >> h);
        }
    }

    void _recalc_above(int i) {
        while (i > 1) {
            i >>= 1;
            X[i] = X_f(_eval_at(i << 1), _eval_at(i << 1 | 1));
        }
    }

    void set_val(int i, std::tuple<int, int, int> x) {
        i += N;
        _propagate_above(i);
        X[i] = x;
        A[i] = A_unit;
        _recalc_above(i);
    }

    std::tuple<int, int, int> fold(int L, int R) {
        L += N;
        R += N;
        _propagate_above(L / (L & -L));
        _propagate_above(R / (R & -R) - 1);
        auto vL = X_unit;
        auto vR = X_unit;
        while (L < R) {
            if (L & 1) {
                vL = X_f(vL, _eval_at(L));
                ++L;
            }
            if (R & 1) {
                --R;
                vR = X_f(_eval_at(R), vR);
            }
            L >>= 1;
            R >>= 1;
        }
        return X_f(vL, vR);
    }

    void operate_range(int L, int R, int x) {
        L += N;
        R += N;
        int L0 = L / (L & -L);
        int R0 = R / (R & -R) - 1;
        _propagate_above(L0);
        _propagate_above(R0);
        while (L < R) {
            if (L & 1) {
                A[L] = A_f(A[L], x);
                ++L;
            }
            if (R & 1) {
                --R;
                A[R] = A_f(A[R], x);
            }
            L >>= 1;
            R >>= 1;
        }
        _recalc_above(L0);
        _recalc_above(R0);
    }

private:
    int N;
    std::vector<std::tuple<int, int, int>> X;
    std::vector<int> A;
};

std::tuple<int, int, int> LazySegTree::X_unit = std::make_tuple(0, 0, 0);
int LazySegTree::A_unit = 0;

int main() {
    int N, Q;
    std::cin >> N >> Q;

    LazySegTree seg(N);
    std::vector<std::tuple<int, int, int>> seq(N, std::make_tuple(1, 0, 0));
    seg.build(seq);

    int score_A = 0, score_B = 0;
    for (int i = 0; i < Q; ++i) {
        int x, L, R;
        std::cin >> x >> L >> R;
        ++R;
        if (x == 0) {
            auto [_, a, b] = seg.fold(L, R);
            if (a > b) {
                score_A += a;
            } else if (b > a) {
                score_B += b;
            }
        } else {
            seg.operate_range(L, R, x);
        }
    }

    auto [_, a, b] = seg.fold(0, N);
    std::cout << score_A + a << " " << score_B + b << std::endl;

    return 0;
}
0