結果

問題 No.789 範囲の合計
ユーザー InTheBloomInTheBloom
提出日時 2024-05-04 04:31:34
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 139 ms / 1,000 ms
コード長 7,198 bytes
コンパイル時間 6,558 ms
コンパイル使用メモリ 210,560 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-05-04 04:31:43
合計ジャッジ時間 9,106 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 139 ms
6,144 KB
testcase_03 AC 137 ms
5,376 KB
testcase_04 AC 136 ms
6,400 KB
testcase_05 AC 122 ms
6,016 KB
testcase_06 AC 126 ms
6,144 KB
testcase_07 AC 103 ms
5,376 KB
testcase_08 AC 116 ms
6,784 KB
testcase_09 AC 111 ms
6,528 KB
testcase_10 AC 136 ms
5,376 KB
testcase_11 AC 110 ms
6,272 KB
testcase_12 AC 111 ms
6,400 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

void main () {
    import std;

    // yosupojudge_PointAddRangeSum();
    // ABC185F();
    yukicoder789();
}

void yukicoder789 () {
    import std;

    int len = 10^^9;
    auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len);
    int n = readln.chomp.to!int;

    long ans = 0;
    foreach (i; 0..n) {
        auto input = readln.split.to!(int[]);
        if (input[0] == 0) {
            int x = input[1], y = input[2];
            seg.set(x, seg.get(x) + y);
        }

        if (input[0] == 1) {
            int l = input[1], r = input[2];
            ans += seg.prod(l, r + 1);
        }
    }

    writeln(ans);
}

void ABC185F () {
    import std;

    int len = 10^^9;
    auto seg = new DynamicSegmentTree!(long, (long a, long b) => a ^ b, () => 0L)(len);
    int N, Q; readln.read(N, Q);
    auto A = readln.split.to!(int[]);
    foreach (i; 0..N) seg.set(i, A[i]);
    foreach (i; 0..Q) {
        int T, X, Y; readln.read(T, X, Y);
        if (T == 1) {
            X--;
            A[X] ^= Y;
            seg.set(X, A[X]);
        }

        if (T == 2) {
            X--, Y--;
            writeln(seg.prod(X, Y + 1));
        }
    }
}

void yosupojudge_PointAddRangeSum () {
    import std;

    int N, Q; readln.read(N, Q);
    auto a = readln.split.to!(int[]);
    auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(10^^9);

    foreach (i; 0..N) {
        seg.set(i, a[i]);
    }

    foreach (i; 0..Q) {
        auto input = readln.split.to!(int[]);
        if (input[0] == 0) {
            int p = input[1], x = input[2];
            seg.set(p, seg.get(p) + x);
        }

        if (input[0] == 1) {
            int l = input[1], r = input[2];
            writeln(seg.prod(l, r));
        }
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

import std.traits : ReturnType, isCallable, Parameters;
import std.meta : AliasSeq;

class DynamicSegmentTree (T, alias op, alias e) {
    // TODO: assertのメッセージを表示
    static assert(isCallable!(op));
    static assert(isCallable!(e));
    static assert(is (ReturnType!(op) == T));
    static assert(is (ReturnType!(e) == T));
    static assert(is (Parameters!(op) == AliasSeq!(T, T)));
    static assert(is (Parameters!(e) == AliasSeq!()));

    // 内部が1-indexedで動的な完全二分セグメント木
    import std.format : format;
    public:
        this (long N_)
        in { assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18)); }
        do {
            length = N_;

            // N_以上の2冪に設定
            N = 1;
            while (N < N_) N *= 2;
        }

        void set (long idx, T val)
        in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
        do {
            idx++;
            internal_set(&root, idx, val, 1, N + 1);
        }

        T get (long idx)
        in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
        do {
            idx++;
            return internal_get(root, idx, 1, N + 1);
        }

        T prod (long l, long r)
        in {
            assert(0 <= l && l < length, format("Dynamic SegmentTree: l = %s does not satisfy constraints. l must be in range of [0, %s)", l, length));
            assert(0 <= r && r <= length, format("Dynamic SegmentTree: r = %s does not satisfy constraints. r must be in range of [0, %s]", r, length));
            assert(l <= r, format("Dynamic SegmentTree: l = %s, r = %s does not satisfy constraints. l <= r must be satisfied.", l, r));
        }
        do {
            l++, r++;
            if (l == r) return e();
            return internal_prod(root, l, r, 1, N + 1);
        }

        T all_prod () {
            return internal_prod(root, 1, N + 1, 1, N + 1);
        }

    private:
        struct node {
            long index;
            T value, product;
            node *left = null, right = null;
        }

        void node_update (node *n) {
            n.product = op(
                    op((n.left == null ? e() : n.left.product), n.value),
                    (n.right == null ? e() : n.right.product)
                    );
        }

        node *root = null;
        long N = 0;
        long length = 0;

        node *[60] stack;

        // [l, r) : 今見ている部分木が管理する範囲
        void internal_set (node **root, long idx, T val, long l, long r) {
            import std.algorithm : swap;
            node *cur = *root;
            node **ptr = root;

            int lat = 0;
            if (cur != null) stack[lat++] = cur;

            while (true) {
                if (cur == null) {
                    import core.stdc.stdlib : malloc;
                    *ptr = cast(node *) malloc(node.sizeof);
                    (*ptr).index = idx; (*ptr).value = (*ptr).product = val; (*ptr).left = (*ptr).right = null;
                    break;
                }
                if (cur.index == idx) {
                    cur.value = val;
                    break;
                }

                long mid = (l + r) / 2;
                if (idx < mid) {
                    if (cur.index < idx) { swap(cur.value, val); swap(cur.index, idx); }
                    r = mid;
                    ptr = &(cur.left);
                    cur = cur.left;

                    if (cur != null) stack[lat++] = cur;
                }
                else {
                    if (idx < cur.index) { swap(cur.value, val); swap(cur.index, idx); }
                    l = mid;
                    ptr = &(cur.right);
                    cur = cur.right;

                    if (cur != null) stack[lat++] = cur;
                }
            }

            foreach_reverse (i; 0..lat) {
                node_update(stack[i]);
            }
        }

        T internal_get (node *cur, long idx, long l, long r) {
            while (true) {
                if (cur == null) return e();
                if (cur.index == idx) return cur.value;

                long mid = (l + r) / 2;
                if (idx < mid) {
                    cur = cur.left;
                    r = mid;
                }
                else {
                    cur = cur.right;
                    l = mid;
                }
            }
            assert(0);
        }

        // [a, b) = 要求区間
        T internal_prod (const node *cur, long a, long b, long l, long r) {
            if (cur == null || b <= l || r <= a) return e();
            if (a <= l && r <= b) return cur.product;

            long mid = (l + r) / 2;
            T res = internal_prod(cur.left, a, b, l, mid);
            if (a <= cur.index && cur.index < b) res = op(res, cur.value);
            res = op(res, internal_prod(cur.right, a, b, mid, r));
            return res;
        }
}
0