PBCSEQ (Segment Tree)

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N = 1e6 + 1;
typedef pair <int, int> ii;

ii e[N];
int n, x[N], sl = 0;
long long bit[N], f[N];

void update(int u, long long val)
{
    while (u <= sl * 2) {
        bit[u] = max(bit[u], val);
        u += u&(-u);
    }
}

int get(int u)
{
    long long kq = 0;
    while (u) {
        kq = max(kq, bit[u]);
        u -= u&(-u);
    }
    return kq;
}

void tinh()
{
    int ds = 0;
    for (int i = 1; i <= n; i++)
        e[i].y = -e[i].y;

    sort(e + 1, e + n + 1);
    reverse(e + 1,e + n + 1);

    for (int i = 1; i <= n; i++)
        e[i].y = -e[i].y;

    for (int i = 1; i <= n; i++) {
        int saker = get(e[i].y) + 1;
        update(e[i].y, saker);
        ds = max(ds,saker);
    }

    cout << ds;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int u, v; cin >> u >> v;
        e[i] = ii(u, v);
        x[++sl] = u, x[++sl] = v;
    }

    sort(x + 1, x + sl + 1);

    int slx = 0;
    for (int i = 1; i <= sl; i++)
        if (x[i] != x[i-1])
            x[++slx] = x[i];
    sl = slx;
    for (int i = 1; i <= sl; i++) {
        e[i].x = lower_bound(x+1, x+sl+1, e[i].x) - x;
        e[i].y = lower_bound(x+1, x+sl+1, e[i].y) - x;
    }

    tinh();
}