結果

問題 No.789 範囲の合計
ユーザー InTheBloomInTheBloom
提出日時 2024-04-29 01:59:13
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 203 ms / 1,000 ms
コード長 5,091 bytes
コンパイル時間 6,745 ms
コンパイル使用メモリ 212,072 KB
実行使用メモリ 17,868 KB
最終ジャッジ日時 2024-11-18 00:14:49
合計ジャッジ時間 10,039 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 193 ms
15,228 KB
testcase_03 AC 102 ms
6,820 KB
testcase_04 AC 203 ms
17,868 KB
testcase_05 AC 148 ms
15,184 KB
testcase_06 AC 155 ms
15,280 KB
testcase_07 AC 100 ms
6,820 KB
testcase_08 AC 166 ms
15,308 KB
testcase_09 AC 148 ms
17,860 KB
testcase_10 AC 153 ms
12,660 KB
testcase_11 AC 121 ms
15,340 KB
testcase_12 AC 119 ms
15,184 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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));
    }
}

void main () {
    import std;

    // yukicoder No.789 範囲の合計

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

    // seg.dump();
    // writeln();

    long ans = 0;
    foreach (i; 0..N) {
        int t, l, r; readln.read(t, l, r);
        if (t == 0) {
            seg.set(l, seg.get(l) + r);
        }
        if (t == 1) {
            ans += seg.prod(l, r + 1);
        }
    }

    writeln(ans);
}

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

class DynamicSegmentTree (T, alias ope, alias e) {
    // TODO: assertのメッセージを表示
    static assert(isCallable!(ope));
    static assert(isCallable!(e));
    static assert(is (ReturnType!(ope) == T));
    static assert(is (ReturnType!(e) == T));
    static assert(is (Parameters!(ope) == 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冪に設定
            if ((N_ & (-N_)) == N_) {
                N = N_;
            }
            else {
                // msb+1 bitを立てる
                foreach_reverse (i; 0..63) {
                    if (0 < (N_ & (1L << i))) {
                        N = 1L << (i + 1);
                        break;
                    }
                }
            }

            root = new node(1, N + 1, e(), null, null);
        }

        void set (long idx, T val) {
            idx++;
            internal_set(root, idx, idx + 1, val, 1, N + 1);
        }

        T get (long idx) {
            idx++;
            return internal_prod(root, idx, idx + 1);
        }

        T prod (long l, long r) {
            // 1-indexed
            l++, r++;
            return internal_prod(root, l, r);
        }

        void dump () {
            void dfs (const node *cur) {
                if (cur == null) {
                    return;
                }
                import std.stdio : writefln;
                writefln("range: [%s %s), value: %s", cur.left, cur.right, cur.value);

                dfs(cur.left_child);
                dfs(cur.right_child);
            }
            dfs(root);
        }

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

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

        // [l, r) : 今いる場所の本来あるべき区間
        void internal_set (ref node *cur, long a, long b, T v, long l, long r) {
            // 途中までで切り上げる
            if (cur == null) {
                cur = new node(a, b, v, null, null);
                return;
            }
            if (a == l && b == r) {
                cur.value = v;
                return;
            }

            // 途中で打ち切られたノードを発見
            if (cur.left != l || cur.right != r) {
                T vv = cur.value;
                long ll = cur.left, rr = cur.right;

                // 区間修正 -> 先にあったノードを直す
                cur.left = l;
                cur.right = r;
                internal_set(cur, ll, rr, vv, l, r);
            }

            // 下に潜る
            long mid = (l + r) / 2;
            if (b <= mid) { internal_set(cur.left_child, a, b, v, l, mid); }
            else { internal_set(cur.right_child, a, b, v, mid, r); }

            // 自分の値を更新
            cur.value = ope(
                    (cur.left_child == null ? e() : cur.left_child.value),
                    (cur.right_child == null ? e() : cur.right_child.value));
        }

        T internal_prod (const node *cur, long a, long b) {
            // まだ作られていない = その区間は初期値
            if (cur == null) return e();

            long l = cur.left, r = cur.right;
            if (b <= l || r <= a) return e();

            // 包含
            if (a <= l && r <= b) return cur.value;

            // 部分包含は必要部分を縮めて渡す
            import std.algorithm : min, max;
            a = max(a, l);
            b = min(b, r);

            long mid = (l + r) / 2;
            if (b <= mid) return internal_prod(cur.left_child, a, b);
            if (mid <= a) return internal_prod(cur.right_child, a, b);

            return ope(
                    internal_prod(cur.left_child, a, mid),
                    internal_prod(cur.right_child, mid, b)
                    );
        }
}
0