結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ふーらくたるふーらくたる
提出日時 2018-01-09 01:00:44
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 146 ms / 5,000 ms
コード長 4,731 bytes
コンパイル時間 1,133 ms
コンパイル使用メモリ 75,628 KB
実行使用メモリ 6,404 KB
最終ジャッジ日時 2023-08-25 00:50:34
合計ジャッジ時間 3,650 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 9 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 66 ms
4,824 KB
testcase_10 AC 59 ms
4,380 KB
testcase_11 AC 40 ms
4,380 KB
testcase_12 AC 67 ms
4,688 KB
testcase_13 AC 12 ms
4,376 KB
testcase_14 AC 42 ms
6,144 KB
testcase_15 AC 105 ms
6,312 KB
testcase_16 AC 118 ms
6,192 KB
testcase_17 AC 146 ms
6,156 KB
testcase_18 AC 82 ms
6,204 KB
testcase_19 AC 92 ms
6,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

#define repeat(i, x) for (int i = 0; (i) < (x); (i)++)

using int64 = long long;

struct Element {
    using T = int;
    static inline constexpr T identity() { return 0; }
    static inline T op(const T& a, const T& b) { return a + b; }
};

template <class Object>
struct Operation {
    using T = typename Object::T;
    using M = T;
    static inline constexpr M identity() { return -1; }
    static inline M op(const M& a, const M& b) { return (b == identity()) ? a : b; }
    // mpをaに適用する
    static inline T apply(const M& mp, const int a, int w) { return (mp == identity()) ? a : w * T(mp); }
};

template <class Object, class Operator>
class LazyPropagationSegmentTree {
    const int N;
    const int h;
    using T = typename Object::T;
    using M = typename Operator::M;
    std::vector<T> t;
    std::vector<M> lazy;

    inline int lowest_pow_of_2(int n) {
        int res = 1;
        while (res < n) res <<= 1;
        return res;
    }

    // log2_X <= nを満たす最大のXを計算
    inline int log2(int n) {
        int res = 0;
        while (n >> (res + 1)) res++;
        return res;
    }

    inline void prop_to(int i) {
        t[i] = Object::op(t[2 * i], t[2 * i + 1]);
    }

    inline void eval(int i, int w) {
        if (i < N and lazy[i] != Operator::identity()) {
            t[i] = Operator::apply(lazy[i], t[i], w);

            if (2 * i < N) {
                // 伝搬
                lazy[2 * i] = Operator::op(lazy[2 * i], lazy[i]);
                lazy[2 * i + 1] = Operator::op(lazy[2 * i + 1], lazy[i]);
            } else if (i < N) {
                t[2 * i] = Operator::apply(lazy[i], t[2 * i], w / 2);
                t[2 * i + 1] = Operator::apply(lazy[i], t[2 * i + 1], w / 2);
            }
            lazy[i] = Operator::identity();
        }
    }

    public:

    LazyPropagationSegmentTree(int n)
        : N(lowest_pow_of_2(n)), h(log2(N) + 1),
          t(2 * N, Object::identity()), lazy(N, Operator::identity()) { }

    template <class InputIt>
    LazyPropagationSegmentTree(InputIt first, InputIt last)
        : N(lowest_pow_of_2(std::distance(first, last))),
          h(log2(N) + 1), 
          t(2 * N, Object::identity()),
          lazy(N, Operator::identity()) {
        std::copy(first, last, t + N);
        for (int i = N - 1; i > 0; i--) prop_to(i);
    }

    inline void update(int l, int r, M mp) {
        update(l, r, mp, 1, 0, N);
    }

    inline void update(int l, int r, M mp, int id, int nodel, int noder) {
        // 範囲外
        eval(id, noder - nodel);   // 演算の順序を守るためさきに伝播させる
        if (noder <= l or r <= nodel) return;

        if (id >= N) {  // 葉
            t[id] = Operator::apply(mp, t[id], 1);
            return;
        }

        if (l <= nodel and noder <= r) {
            lazy[id] = Operator::op(lazy[id], mp);
            eval(id, noder - nodel);
        } else {
            update(l, r, mp, 2 * id, nodel, (nodel + noder) / 2);
            update(l, r, mp, 2 * id + 1, (nodel + noder) / 2, noder);
            t[id] = Object::op(t[2 * id], t[2 * id + 1]);
        }
    }

    T get(int i) {
        i += N;
        for (int j = (h - 1); j > 0; j--) eval(i >> j, 1 << j);
        return t[i];
    }

    T query(int l, int r) {
        return query(l, r, 1, 0, N);
    }

    T query(int l, int r, int id, int nodel, int noder) {
        // 範囲外
        eval(id, noder - nodel);        
        if (noder <= l or r <= nodel) return Object::identity();

        // 完全に含まれる
        if (l <= nodel and noder <= r) return t[id];

        T resl = query(l, r, 2 * id, nodel, (nodel + noder) / 2);
        T resr = query(l, r, 2 * id + 1, (nodel + noder) / 2, noder);
        return Object::op(resl, resr);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    static LazyPropagationSegmentTree<Element, Operation<Element>> A(N), B(N);

    int Q; cin >> Q;

    int64 a_score = 0,
          b_score = 0;
    repeat (i, Q) {
        int x, l, r; cin >> x >> l >> r;
        r++;

        if (x == 0) {   // ボーナスチャンス
            int a_cnt = A.query(l, r),
                b_cnt = B.query(l, r);

            if (a_cnt > b_cnt) a_score += a_cnt;
            else if (a_cnt < b_cnt) b_score += b_cnt;
        } else if (x == 1) {
            A.update(l, r, 1);
            B.update(l, r, 0);
        } else {
            A.update(l, r, 0);
            B.update(l, r, 1);
        }
    }
    a_score += A.query(0, N);
    b_score += B.query(0, N);

    cout << a_score << " " << b_score << endl;

    cerr << endl;

    return 0;
}
0