Submission #72196359

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n;
    cin>>n;

    pair<int, int> a[n+5];
    for(int i=1; i<=n; i++){
        cin>>a[i].first>>a[i].second;
        a[i].second *= -1;
    }

    sort(a+1, a+1+n);

    vector<int> b(n);
    for(int i=1; i<=n; i++){
        b[i-1] = -a[i].second;
    }

    cout<<lis(b)<<endl;
	return 0;
}

Submission Info

Judge Result