JAG 夏合宿 Day3 F - Escape from the Hell

問題文は面白かったんですが実装はつらかったです。

問題

jag2016autumn.contest.atcoder.jp

解法

最後に A[i] 登るところ以外は, 明らかに D[j] = A[j] - B[j] が大きい順に使うのが最適です。この j をどこまで使うかで場合分けします。

j の最大値も j < i を満たす場合
あらかじめ sumD[i] = D[0] + D[1] + ... + D[i-1], sumC[i] = C[0] + ... + C[i-1] を計算して, sumD[ok] > sumC[ok] を満たす ok の最大値を覚えておきます。
A[i] + sumD[j] >= L を満たす j の最小値のうち, j <= ok となるものがあれば j+1 は解の候補です。

j の最大値が j > i を満たす場合
こっちが少しめんどくさいです。

この場合の上り方を見ると, 以下のようになっています。

D[0] D[1] D[2] ... D[i-1] D[i+1] ... D[j]
C[0] C[1] C[2] ... C[i-1] C[i] ... C[j-1]

よって, seg[i] = sumD[i] - sumC[i-1] というものを覚えておいて, min(seg[i+1], seg[i+2], ..., seg[j]) - D[i] > 0 でありかつ i-1 <= ok であれば良いです。

// セグメント木(RMQ 対応)
// update: k 番目の値を a に変更
// query: [l, r) の区間の最大値を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, numeric_limits<T>::max());
    }
    inline T merge(T x, T y) {
        return min(x, y);
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return numeric_limits<T>::max();
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

const int INF = 1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, L;
    cin >> N >> L;
    vector<pii> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i].first >> P[i].second;
    }
    sort(P.begin(), P.end(), [](const pii& lhs, const pii& rhs){
        if (lhs.first-lhs.second == rhs.first-rhs.second) return lhs.first < rhs.first;
        return lhs.first-lhs.second > rhs.first-rhs.second;
    });
    vector<int> A(N), B(N), D(N);
    for (int i = 0; i < N; i++) {
        A[i] = P[i].first;
        B[i] = P[i].second;
        D[i] = A[i] - B[i];
    }
    vector<int> C(N);
    for (int i = 0; i < N; i++)
        cin >> C[i];
    vector<ll> sumD(N+1), sumC(N+1);
    for (int i = 0; i < N; i++) {
        sumD[i+1] = sumD[i] + D[i];
        sumC[i+1] = sumC[i] + C[i];
    }
    int ok = -1;
    for (int i = 1; i <= N; i++) {
        if (sumD[i] - sumC[i] > 0) {
            ok = i-1;
        } else break;
    }
    // cout << "A B" << endl;
    // for (int i = 0; i < N; i++) {
    //     cout << A[i] << " " << B[i] << endl;
    // }
    // cout << endl;
    // cout << "ok" << endl;
    // cout << ok << endl << endl;
    int ans = INF;
    {
        int maxi = 0;
        for (int i = N-1; i >= 0; i--) {
            maxi = max(maxi, A[i]);
            if (i-1 <= ok && maxi + sumD[i] >= L) ans = min(ans, i+1);
        }
    }
    ST<ll> seg(N+1);
    for (int i = 1; i <= N; i++) {
        seg.update(i, sumD[i] - sumC[i-1]);
    }
    for (int i = 0; i <= min(ok+1, N-2); i++) {
        // (low, high]
        int high = N-1, low = i;
        while (high - low > 1) {
            const int med = (high+low) / 2;
            if (sumD[med+1] + B[i] >= L) high = med;
            else low = med;
        }
        if (sumD[high+1] + B[i] < L) continue;
        //cout << i << " " << high << endl;
        //cout << seg.query(i+1, high+2) << endl;
        if (seg.query(i+1, high+2) > D[i]) ans = min(ans, high+1);
    }
    //cout << endl;
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}