CS Academy Round #41: E. Candles

,

https://csacademy.com/contest/round-41/task/candles/

これを解いた時点では全体$8$位で日本人内だとuwiさんやantaさんを下して$1$位だった。 思わずスクリーンショット取ってしまった。

その後はFが解けなかったのでもちろん抜かれたが、rating +84して赤色になった。CSAの赤の価値は分からないにせよ始めての赤。嬉しい。

problem

長さ$h_i$を持ったろうそくがいくつかある。 毎晩$c_j$本のろうそくを灯し、使われたろうそくは長さが$1$減る。 灯せなかったらそこで終了。最大何日灯せるか。

solution

常にろうそくを長い順に$c_j$個使うのが最適。 遅延伝播segment木をいい感じに使って$O(N \log N + M (\log N)^2)$

単純にやると$O(MN \log N)$であり、定数倍高速化はかなり厳しそう。 区間へのクエリであるのでsegment木が思い出されるが、sortはなおも必要。 ここで減少量が常に$1$であることを使う。 引いた後のsortは元々同じ数だった区間を反転させるだけなので、操作する区間を分けて反転を不要にする。 例えば112222333という列から$5$個使うなら1122*****と引いて112211222とするのではなく11**22***と引けば111122222。 諸々の位置は二分探索する。

ついでに、減少量が常に$K$以下と一般化された場合は実質的に上を$K$回やることになりそう。 気合いで細かく実装して定数倍改善はあるだろうけれど。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef OperatorMonoid monoid_type;
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n-1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i-1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i-n+1] = op.apply(z, a[i-n+1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
        }
    }
};
struct plus_operator_t {
    typedef int underlying_type;
    typedef int target_type;
    int unit() const { return 0; }
    int append(int a, int b) const { return a + b; }
    int apply(int a, int b) const { return a + b; }
};

template <typename UnaryPredicate>
ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone
    -- l;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> h(n); repeat (i, n) scanf("%d", &h[i]);
    vector<int> c(m); repeat (i, m) scanf("%d", &c[i]);
    // solve
    sort(whole(h));
    dual_segment_tree<plus_operator_t> segtree(n, 0);
    repeat (i, n) {
        segtree.range_apply(i, i + 1, h[i]);
    }
    int result = 0;
    for (; result < m; ++ result) {
        int c_i = c[result];
        int k = segtree.point_get(n - c_i);
        if (k == 0) break;
        int l = binsearch(0, n - c_i, [&](int j) {
            return segtree.point_get(j) >= k;
        });
        int r = binsearch(n - c_i, n, [&](int j) {
            return segtree.point_get(j) > k;
        });
        segtree.range_apply(r, n, -1);
        segtree.range_apply(l, l + (c_i - (n - r)), -1);
    }
    // output
    printf("%d\n", result);
    return 0;
}