Submission #3053920

---

Source Code Expand

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

void compute() {

}

struct Data {
  int x,y;
  bool operator < ( const Data & d ) const {
    if( x != d.x ) return x < d.x;
    return y < d.y;
  }
};

#define MAX 100100
int dp[MAX];
int main() {
  int n;
  cin >> n;
  vector<Data> vec(n);
  rep(i,n) cin >> vec[i].x >> vec[i].y;
  sort(ALL(vec));
  rep(i,n) {
    int sp = i;
    while( i + 1 < n && vec[i+1].x == vec[sp].x ) {
      ++i;
    }
    //cout << sp << "->" << i << endl;
    reverse(vec.begin()+sp,vec.begin()+i+1);
  }
  //rep(i,n) cout << vec[i].x << "," << vec[i].y << " "; puts("");
  rep(i,n+1) dp[i] = INT_MAX;
  rep(i,n) *upper_bound(dp,dp+n,vec[i].y) = vec[i].y;
  cout << (lower_bound(dp,dp+n,INT_MAX)-dp) << endl;
  
  compute();
  return 0;
}

Submission Info

Judge Result