E - Tough Journey

E - Tough Journey

解法
安いところでたくさん買いたいので、貪欲に考えたくなる。

考えると
今いる場所をiとして
K以内の距離でiより安く買える地点がいくつかあるなら、その中の最も近い地点jで買ったほうが得なので、jまで行ける程度に買い、jに飛べばいい

もし、K以内の距離に自分より安いものが無いなら、K個進んでペットボトルが尽きたときにiより高い値段で買わないといけなくなるため、
iでK本を買い込む必要がある
また、この際K以内で最も安い（マシ）地点jに着くまでは何も買う必要はないので、jまで飛べる

iが上下どっちに属するかは、セグメント木でO(log n)で分かる
もしiが上の場合、for文でiから順番に見ていってA[i]より小さくなった地点をjとするやり方で間に合う（jまで飛べるため、一回確認した場所を後で確認することが無いため）

よって、O(n log n)でこの問題が解けた

Submission #3785587 - CODE FESTIVAL 2018 Final (Parallel)

vi A, B, C;
ll SEGIN = MAX(ll);
struct Monoid {
    int i;
    ll v;
    Monoid(int i, ll v) : i(i), v(v) {}
    Monoid operator*(Monoid &r) const {
        return r.v == SEGIN || v <= r.v ? *this : r;    //左寄りの最小値
//        return r.v == SEGIN || v < r.v ? *this : r;     //右寄りの最小値
//        return r.v == SEGIN || v >= r.v ? *this : r;    //左寄りの最大値
//        return r.v == SEGIN || v > r.v ? *this : r;    //右寄りの最大値
//        return SegNode(i + r.i, (v == SEGIN ? 0 : v) + (r.v == SEGIN ? 0 : r.v));//長さ,区間和
    }
} e(-1, SEGIN);
struct SegmentTree {
    int n;
    vector<Monoid> seg;
    void update(int k, int v) {
        seg[k + n - 1] = Monoid(k, v);
        k += n - 1;
        while (k) {
            k = (k - 1) / 2;
            seg[k] = seg[k * 2 + 1] * seg[k * 2 + 2];
        }
    }
    SegmentTree(int len) {
        n = 1;
        while (n < len)n *= 2;
        seg.assign(2 * n - 1, e);
    }
    SegmentTree(vi dat) {
        n = 1;
        while (n < dat.size())n *= 2;
        seg.assign(2 * n - 1, e);
        rep(i, dat.size()) {
            update(i, dat[i]);
        }
    }
    Monoid query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)return e;
        else if (a <= l && r <= b)return seg[k];
        else {
            Monoid sl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            Monoid sr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return sl * sr;
        }
    }
    //abはハミ出た範囲でも渡せる
    Monoid query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
    int geti(int a, int b) {
        return query(a, b).i;
    }
    ll getv(int a, int b) {
        return query(a, b).v;
    }
    Monoid operator[](int k) const {
        return seg[k * n];
    }
};
signed main() {
    cin >> N >> K;
    addAll(A, N);
    A.push_back(0);
    SegmentTree seg(A);
    int pet = 0;
    int res = 0;
    //Nはあくまでゴール
    rep(i, N) {
        auto to = seg.query(i + 1, i + K);
        int minv = to.v;
        int mini = to.i;
        //自分より小さいものがあれば
        // 一番近く自分以下のところへ行ける程度に買う
        if (A[i] >= minv) {
            rep(j, i + 1, N + 1) {
                if (A[i] >= A[j]) {
                    int dis = j - i;
                    if (pet < dis) {
                        res += A[i] * (dis - pet);
                        pet = dis;
                    }
                    pet -= dis;
                    i = j - 1;
                    break;
                }
            }
        } else {
            //自分より大きいのしか無ければ
            //今買い込み、一番マシなところへ行く
            res += A[i] * (K - pet);
            int dis = mini - i;
            pet = K - dis;
            i = mini - 1;
        }
    }
    cout << res << endl;
    return 0;
}