結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー PachicobuePachicobue
提出日時 2018-11-21 02:12:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,741 bytes
コンパイル時間 2,261 ms
コンパイル使用メモリ 208,100 KB
実行使用メモリ 17,216 KB
最終ジャッジ日時 2023-08-26 02:32:09
合計ジャッジ時間 5,549 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 84 ms
16,908 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 139 ms
17,008 KB
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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<ll, ll>;  // (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()
{
    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 + b2, one = num - two + b1;
    std::cout << one << " " << two << std::endl;
    return 0;
}
0