mayoko’s diary

プロコンとかいろいろ。

AtCoder Beginner Contest 038 D - プレゼント

解法

これ想定解かな…セグメント木を適当に使ったら解けました。

まず (h, w) のペアの順番にソートします。基本的にはこれで dp[i] = (i までの箱を使って最高いくつの入れ子を作れるか) というのを求めていきます。これで (hi, wi) を順番に見ていくことによって, h については考えなくても i < j を満たす (i, j) について hi < hj が保証されています。なので後は w についてだけです。

(hi, wi) について調べるときは, [0, wi) について dp の値が最高のものを取っていけば良いですが, これはセグメント木で実現できます。

一つ注意なのは, h の大きさが同じものについては, 逐一更新せずすべての dp を求めてから一気に更新しないといけないことに注意です。

// セグメント木(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, 0);
    }
    inline T merge(T x, T y) {
        return max(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 0;
        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 MAXN = 100100;
pair<int, int> P[MAXN];
int dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> P[i].first >> P[i].second;
    sort(P, P+N);
    ST<int> seg(MAXN);
    int ans = 0;
    for (int i = 0; i < N; ) {
        int ni = i+1;
        while (ni < N && P[i].first == P[ni].first) ni++;
        for (int j = i; j < ni; j++) {
            dp[j] = 1 + seg.query(0, P[j].second);
            ans = max(ans, dp[j]);
        }
        for (int j = i; j < ni; j++) {
            seg.update(P[j].second, max(dp[j], seg.query(P[j].second, P[j].second+1)));
        }
        i = ni;
    }
    cout << ans << endl;
    return 0;
}