結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー PachicobuePachicobue
提出日時 2018-11-21 02:19:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 140 ms / 5,000 ms
コード長 4,798 bytes
コンパイル時間 2,142 ms
コンパイル使用メモリ 209,000 KB
実行使用メモリ 16,944 KB
最終ジャッジ日時 2023-08-26 02:32:16
合計ジャッジ時間 4,582 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 8 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 66 ms
9,848 KB
testcase_10 AC 53 ms
4,376 KB
testcase_11 AC 37 ms
6,752 KB
testcase_12 AC 64 ms
9,872 KB
testcase_13 AC 11 ms
4,380 KB
testcase_14 AC 40 ms
16,908 KB
testcase_15 AC 102 ms
16,840 KB
testcase_16 AC 110 ms
16,804 KB
testcase_17 AC 140 ms
16,944 KB
testcase_18 AC 76 ms
16,872 KB
testcase_19 AC 86 ms
16,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define show(x) std::cerr << #x << " = " << x << std::endl
using ll = long long;
using ull = unsigned long long;
template <typename T>
constexpr T INF = std::numeric_limits<T>::max() / 10;
constexpr std::size_t PC(ull v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<std::size_t>(v * 0x0101010101010101ULL >> 56 & 0x7f); }
constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); }
constexpr ull SZ(const ull v) { return 1ULL << LG(v); }
template <typename Base>
class LazySegmentTree
{
public:
    using BaseAlgebra = Base;
    using ValMonoid = typename BaseAlgebra::ValMonoid;
    using OpMonoid = typename BaseAlgebra::OpMonoid;
    using T = typename BaseAlgebra::T;
    using F = typename BaseAlgebra::OpMonoid::T;
    LazySegmentTree(const std::size_t n) : data_num(n), half(SZ(n)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) {}
    template <typename InIt>
    LazySegmentTree(const InIt first, const InIt last) : data_num(distance(first, last)), half(SZ(data_num)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id())
    {
        copy(first, last, value.begin() + half);
        for (std::size_t i = half - 1; i >= 1; i--) { up(i); }
    }
    T accumulate(const std::size_t L, const std::size_t R) const
    {
        auto arec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> T {
            if (L <= left and right <= R) {
                return value[index];
            } else if (right <= L or R <= left) {
                return ValMonoid::id();
            } else {
                return act(action[index], acc(self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right)));
            }
        };
        return arec(arec, 1, 0, half);
    }
    void modify(const std::size_t L, const std::size_t R, const F& f)
    {
        auto mrec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> void {
            if (L <= left and right <= R) {
                this->update(index, f);
            } else if (right <= L or R <= left) {
            } else {
                this->update(index << 1, action[index]), this->update(index << 1 | 1, action[index]);
                self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right);
                this->up(index), action[index] = OpMonoid::id();
            }
        };
        mrec(mrec, 1, 0, half);
    }

private:
    void up(const std::size_t i) { value[i] = acc(value[i << 1], value[i << 1 | 1]); }
    void update(const std::size_t i, const F& f) { value[i] = act(f, value[i]), action[i] = compose(f, action[i]); }
    const std::size_t data_num, half;
    std::vector<T> value;
    std::vector<F> action;
    const ValMonoid acc{};
    const OpMonoid compose{};
    const BaseAlgebra act{};
};
struct Sum_Set
{
    using X = ll;
    using T = std::pair<X, X>;  // (value, num)
    struct ValMonoid
    {
        T operator()(const T& a, const T& b) const { return {a.first + b.first, a.second + b.second}; }
        static constexpr T id() { return {0, 0}; }
    };
    struct OpMonoid
    {
        using T = X;
        T operator()(const T& f1, const T& f2) const { return (f1 != INF<T>) ? f1 : f2; }
        static constexpr T id() { return INF<T>; }
    };
    T operator()(const OpMonoid::T& f, const T& x) const { return (f != INF<X>) ? T{x.second * f, x.second} : x; }
};
int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int N, Q;
    std::cin >> N >> Q;
    using T = Sum_Set::T;
    std::vector<T> v(N, {0, 1});
    LazySegmentTree<Sum_Set> seg1(v.begin(), v.end()), seg2(v.begin(), v.end());
    ll b1 = 0, b2 = 0;
    for (int q = 0, x, l, r; q < Q; q++) {
        std::cin >> x >> l >> r;
        if (x == 0) {
            const ll sum = seg1.accumulate(l, r + 1).first;
            const ll num = seg2.accumulate(l, r + 1).first;
            const ll two = sum - num, one = num - two;
            if (two != one) { (two > one ? b2 : b1) += std::max(two, one); }
        } else if (x == 1) {
            seg1.modify(l, r + 1, 1), seg2.modify(l, r + 1, 1);
        } else {
            seg1.modify(l, r + 1, 2), seg2.modify(l, r + 1, 1);
        }
    }
    const ll sum = seg1.accumulate(0, N).first;
    const ll num = seg2.accumulate(0, N).first;
    const ll two = sum - num, one = num - two;
    std::cout << one + b1 << " " << two + b2 << std::endl;
    return 0;
}
0