Submission #1627815

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N;
P wh[101010];

int h[101010];

int dp[101010];

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> wh[i].first >> wh[i].second;
    }

    sort(wh, wh + N);
    /*
    cout << "###" << endl;
    REP(i,N) {
        cout << wh[i].first << " : " << wh[i].second << endl;
    }
    */

    int newN = 0;
    int pre = wh[0].first;
    h[newN++] = wh[0].second;
    for (int i=1; i<N; i++) {
        if (wh[i].first != pre) {
            h[newN++] = wh[i].second;
        }
        pre = wh[i].first;
    }


    //REP(i,newN) cout << h[i] << " ";
    //cout << endl;

    fill(dp, dp + newN, INF);
    REP(i,newN) {
        *lower_bound(dp, dp + newN, h[i]) = h[i];
    }

    cout << (lower_bound(dp, dp + newN, INF) - dp) << endl;
}

Submission Info

Judge Result