Submission #2123227

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

const int WMAX=100000;
const int INF=INT_MAX/2;
int bit[WMAX+1], N;
vector<pair<int,int>> v;

int main(){
  cin>>N;
  for(int i=0;i<N;i++){
    int w,h;
    cin>>w>>h;
    v.push_back(make_pair(w,-h));
  }
  sort(v.begin(),v.end());
  for(int i=0;i<N;i++) v[i].second*=-1;
  int dp[N];
  fill(dp,dp+N,INF);
  for(int i=0;i<N;i++){
    int ind=lower_bound(dp,dp+N,v[i].second)-dp;
    dp[ind]=v[i].second;
  }
  for(int i=N-1;i>=0;i--){
    if(dp[i]<INF){
      cout<<i+1<<endl;
      return 0;
    }
  }
}

Submission Info

Judge Result