#1005667 (D) No.2859 Falling Balls

• 問題: No.2859 Falling Balls
• ユーザー: InTheBloom
• 提出日時: 2024-08-30 11:13:29
• 言語: D (dmd 2.109.1)
• 結果: WA
• 実行時間: -
• コード長: 6,788 bytes
• コンパイル時間: 7,746 ms
• コンパイル使用メモリ: 214,824 KB
• 実行使用メモリ: 14,016 KB
• 最終ジャッジ日時: 2024-08-30 11:13:44
• 合計ジャッジ時間: 13,696 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 9 WA * 1 TLE * 1 -- * 19

ソースコード

import std;

void main () {
    int N, K; readln.read(N, K);
    auto T = readln.split.to!(int[]);
    auto X = readln.split.to!(int[]);
    auto C = readln.split.to!(int[]);

    // まあdpしかなさそう。
    // 普通にやるとO(N^2)どうにかしてセグメント木とかに載せたい。
    // 配る遷移よりもらう遷移の方が濃厚。

    // K = 1を考えてみる。T-X平面上でもらう対象になる領域は(Ti, Xi)を頂点とした二等辺三角形になる。
    // -> 座標軸を45度回転すると、これは右下領域に変換できる。(これはややこしい計算を行うというより、y = x及びy = -xが変換後に座標軸となることから類推できる。)
    // -> 二次元平面状でのstatic rectangle sum(モノイド)を行う問題に帰着できる。
    // -> 任意の矩形領域ではなく、片側が(-inf, -inf)固定なので逆元が必要ない。平面走査で解ける。
    // -> 1 < Kの場合も同様に変換できるらしい。知らん。

    // 縦軸側をTにして考える。
    // 座標変換
    // X = x + y
    // Y = x - y
    // を用いて変換

    auto x = new long[](N);
    auto y = new long[](N);

    foreach (i; 0..N) {
        x[i] = X[i] - 1L * K * T[i];
        y[i] = X[i] + 1L * K * T[i];
    }

    auto index = iota(N).array;
    bool less (int a, int b) {
        if (y[a] == y[b]) return x[a] < x[b];
        return y[a] < y[b];
    }
    index.sort!(less);

    // 動的セグメント木による平面走査
    const long pad = 10 ^^ 9;
    auto rMq = new DynamicSegmentTree!(long, (long a, long b) => max(a, b), () => -long.max)(10L ^^ 15);
    rMq.set(pad, 0);

    auto dp = new long[](N);
    dp[] = -long.max;

    foreach (i; index) {
        long p = rMq.prod(x[i] + pad, 10L ^^ 15);
        if (-long.max < p) dp[i] = p + C[i];

        rMq.set(x[i] + pad, max(rMq.get(x[i] + pad), dp[i]));
    }

    long ans = -long.max;
    foreach (i; 0..N) ans = max(ans, dp[i]);

    writeln(ans);
}

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;

        // [l, r) : 今見ている部分木が管理する範囲
        node *internal_set (ref node *cur, long idx, T val, long l, long r) {
            if (cur == null) {
                return cur = new node(idx, val, val, null, null);
            }

            if (cur.index == idx) {
                cur.value = val;
                node_update(cur);
                return cur;
            }

            // 既に部分木管理ノードが存在するときの処理
            import std.algorithm : swap;

            long mid = (l + r) / 2;
            if (idx < mid) {
                // 今いる人を押しのける
                if (cur.index < idx) { swap(cur.value, val); swap(cur.index, idx); }
                cur.left = internal_set(cur.left, idx, val, l, mid);
            }
            else {
                if (idx < cur.index) { swap(cur.value, val); swap(cur.index, idx); }
                cur.right = internal_set(cur.right, idx, val, mid, r);
            }

            node_update(cur);
            return cur;
        }

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

            long mid = (l + r) / 2;
            if (idx < mid) return internal_get(cur.left, idx, l, mid);
            return internal_get(cur.right, idx, mid, r);
        }

        // [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;
        }
}