Submission #3453360

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<climits>
#include<utility>
#include<vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    pair<int, int> boxes[n];
    for(int i=0;i<n;i++) cin >> boxes[i].first >> boxes[i].second;
    sort(boxes, boxes+n);

    int w = -1;
    vector<int> h;
    for(int i=0;i<n;i++) {
        if(w < boxes[i].first) {
            h.push_back(boxes[i].second);
            w = boxes[i].first;
        }
    }

    int dp[n];
    fill(dp, dp+n, INT_MAX);
    for(int i=0;i<h.size();i++) {
        if(i && h[i] == h[i-1]) continue;
        int k = upper_bound(dp, dp+n, h[i]) - dp;
        dp[k] = h[i];
    }
    int ans = lower_bound(dp, dp+n, INT_MAX) - dp;
    cout << ans << endl;
}

Submission Info

Judge Result