#225742 (C++17) No.619 CardShuffle

提出ソース

結果

問題	No.619 CardShuffle
ユーザー	Pachicobue
提出日時	2017-12-23 22:14:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,079 ms / 3,000 ms
コード長	8,617 bytes
コンパイル時間	2,423 ms
コンパイル使用メモリ	220,872 KB
実行使用メモリ	8,768 KB
最終ジャッジ日時	2023-08-24 15:16:39
合計ジャッジ時間	24,578 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	3 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	3 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	3 ms 4,376 KB
testcase_09	AC	3 ms 4,376 KB
testcase_10	AC	2 ms 4,504 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	3 ms 4,376 KB
testcase_16	AC	1,051 ms 8,768 KB
testcase_17	AC	1,029 ms 8,576 KB
testcase_18	AC	1,064 ms 8,668 KB
testcase_19	AC	1,021 ms 8,564 KB
testcase_20	AC	1,027 ms 8,512 KB
testcase_21	AC	1,027 ms 8,652 KB
testcase_22	AC	983 ms 8,652 KB
testcase_23	AC	1,000 ms 8,540 KB
testcase_24	AC	986 ms 8,604 KB
testcase_25	AC	976 ms 8,472 KB
testcase_26	AC	1,072 ms 8,464 KB
testcase_27	AC	1,078 ms 8,544 KB
testcase_28	AC	1,078 ms 8,596 KB
testcase_29	AC	1,079 ms 8,644 KB
testcase_30	AC	1,068 ms 8,668 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	1,027 ms 8,660 KB
testcase_33	AC	1,052 ms 8,580 KB
testcase_34	AC	1,043 ms 8,536 KB
testcase_35	AC	849 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

constexpr ll MOD = (ll)1e9 + 7LL;

template <typename Base>
class SegmentTree
{
public:
    using BaseAlgebra = Base;
    using AccMonoid = typename BaseAlgebra::AccMonoid;
    using OpMonoid = typename BaseAlgebra::OpMonoid;
    using T = typename BaseAlgebra::T;
    using F = typename BaseAlgebra::OpMonoid::T;

    SegmentTree(const int n) : data_num(n), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size, AccMonoid::identity()), action(size, OpMonoid::identity()) { assert(n > 0); }
    SegmentTree(const std::vector<T>& val) : data_num(val.size()), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size), action(size, OpMonoid::identity())
    {
        for (int data = 0; data < half; data++) {
            if (data < data_num) {
                value[data + half] = val[data];
            } else {
                value[data + half] = AccMonoid::identity();
            }
        }
        for (int node = half - 1; node >= 1; node--) {
            value[node] = acc(value[2 * node], value[2 * node + 1]);
        }
    }

    T get(const int a) const
    {
        assert(0 <= a and a < data_num);
        return accumulate(a, a + 1);
    }

    void set(const int a, const T& val)
    {
        assert(0 <= a and a < data_num);
        const int node = a + half;
        value[node] = val;
        for (int i = node / 2; i > 0; i /= 2) {
            value[i] = acc(value[2 * i], value[2 * i + 1]);
        }
    }
    void set(const int a, const T&& val)
    {
        assert(0 <= a and a < data_num);
        const int node = a + half;
        value[node] = val;
        for (int i = node / 2; i > 0; i /= 2) {
            value[i] = acc(value[2 * i], value[2 * i + 1]);
        }
    }

    T accumulate(const int a, const int b) const  // Accumulate (a,b]
    {
        assert(0 <= a and a < b and b <= data_num);
        return accumulateRec(1, 0, half, a, b);
    }

    void modify(const int a, const int b, const F& f)  // Apply f on (a,b]
    {
        assert(0 <= a and a < b and b <= data_num);
        if (f == OpMonoid::identity()) {
            return;
        }
        modifyRec(1, 0, half, a, b, f);
    }

private:
    void modifyRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right, const F& f)
    {
        if (mod_left <= int_left and int_right <= mod_right) {
            value[int_index] = act(f, value[int_index]);
            action[int_index] = compose(f, action[int_index]);
        } else if (int_right <= mod_left or mod_right <= int_left) {
            // Do nothing
        } else {
            modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, 0, half, action[int_index]);
            modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right, f);
            modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, 0, half, action[int_index]);
            modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right, f);
            value[int_index] = acc(value[2 * int_index], value[2 * int_index + 1]);
            action[int_index] = OpMonoid::identity();
        }
    }

    T accumulateRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right) const
    {
        if (mod_left <= int_left and int_right <= mod_right) {
            return value[int_index];
        } else if (int_right <= mod_left or mod_right <= int_left) {
            return AccMonoid::identity();
        } else {
            return act(action[int_index], acc(accumulateRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right),
                                              accumulateRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right)));
        }
    }

    const int data_num;  // Num of valid data on leaves.
    const int height;
    const int size;
    const int half;
    vector<T> value;   // Tree for value(length: size)
    vector<F> action;  // Tree for action(length: half)
    bool has_lazy;

    const AccMonoid acc{};
    const OpMonoid compose{};
    const BaseAlgebra act{};
};

struct ProductSum_Nothing {
    using X = ll;
    using T = tuple<ll, ll, ll>;
    struct AccMonoid {
        T operator()(const T& a, const T& b) const
        {
            const ll A = get<0>(a);
            const ll B = get<1>(a);
            const ll C = get<2>(a);
            const ll D = get<0>(b);
            const ll E = get<1>(b);
            const ll F = get<2>(b);
            if (A == -1 and B == -1 and C == -1) {
                return b;
            } else if (D == -1 and E == -1 and F == -1) {
                return a;
            }
            if (A != -1 and C != -1) {
                // (*A+B+C) (*D+E+F) = *A+(B+CD+E)+F
                // (*A+B+C) (*D)     = *A+B+CD
                // (*A+B+C) (+E+F)   = *A+(B+C+E)+F
                if (D != -1 and F != -1) {
                    return make_tuple(A, (B + C * D + E) % MOD, F);
                } else if (D != -1) {
                    return make_tuple(A, B, C * D);
                } else {
                    return make_tuple(A, (B + C + E) % MOD, F);
                }
            } else if (A != -1) {
                // (*A)     (*D+E+F) = *AD+E+F
                // (*A)     (*D)     = *AD
                // (*A)     (+E+F)   = *A+E+F
                if (D != -1 and F != -1) {
                    return make_tuple((A * D) % MOD, E, F);
                } else if (D != -1) {
                    return make_tuple((A * D) % MOD, 0, -1);
                } else {
                    return make_tuple(A, E, F);
                }
            } else {
                // (+B+C)   (*D+E+F) = +(B+CD+E)+F
                // (+B+C)   (*D)     = +B+CD
                // (+B+C)   (+E+F)   = +(B+C+E)+F
                if (D != -1 and F != -1) {
                    return make_tuple(-1, (B + C * D + E) % MOD, F);
                } else if (D != -1) {
                    return make_tuple(-1, B, (C * D) % MOD);
                } else {
                    return make_tuple(-1, (B + C + E) % MOD, F);
                }
            }
        }
        constexpr static T identity() { return make_tuple(-1, -1, -1); }
    };

    struct OpMonoid {
        using T = X;
        T operator()(const T& f1, const T& f2) const { return f1 + f2; }
        static constexpr T identity() { return 0; }
    };

    T operator()(const OpMonoid::T& /*f*/, const T& x) const { return x; }
};


int main()
{
    int N;
    cin >> N;
    const int NUM = (N + 1) / 2;
    const int OP = (N - 1) / 2;
    vector<int> number(NUM, 0);
    vector<bool> op(OP + 1, true);
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (i % 2 == 0) {
            number[i / 2] = c - '0';
        } else {
            op[(i + 1) / 2] = c == '*';
        }
    }
    using T = tuple<ll, ll, ll>;
    vector<T> value(NUM);
    for (int i = 0; i < NUM; i++) {
        value[i] = (op[i] ? make_tuple(number[i], -1, -1) : make_tuple(-1, 0, number[i]));
    }

    SegmentTree<ProductSum_Nothing> seg(value);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        char c;
        cin >> c;
        ll X, Y;
        cin >> X >> Y;
        cerr << c << " " << X << " " << Y << endl;
        if (c == '?') {
            X /= 2, Y /= 2;
            const auto ans = seg.accumulate(X, Y + 1);
            cout << (max(0LL, get<0>(ans)) + max(0LL, get<1>(ans)) + max(0LL, get<2>(ans))) % MOD << endl;
        } else {
            if (X % 2 == 1) {
                X /= 2, Y /= 2;
                const ll vx = op[X] ? get<0>(seg.get(X)) : get<2>(seg.get(X));
                const ll vy = op[Y] ? get<0>(seg.get(Y)) : get<2>(seg.get(Y));
                seg.set(X, (op[X] ? make_tuple(vy, -1LL, -1LL) : make_tuple(-1LL, 0LL, vy)));
                seg.set(Y, (op[Y] ? make_tuple(vx, -1LL, -1LL) : make_tuple(-1LL, 0LL, vx)));
            } else {
                X /= 2, Y /= 2;
                const ll vx = op[X] ? get<0>(seg.get(X)) : get<2>(seg.get(X));
                const ll vy = op[Y] ? get<0>(seg.get(Y)) : get<2>(seg.get(Y));
                swap(op[X], op[Y]);
                seg.set(X, (op[X] ? make_tuple(vx, -1LL, -1LL) : make_tuple(-1LL, 0LL, vx)));
                seg.set(Y, (op[Y] ? make_tuple(vy, -1LL, -1LL) : make_tuple(-1LL, 0LL, vy)));
            }
        }
    }


    return 0;
}

yukicoder

結果

テストケース

ソースコード