LIS - Dãy con tăng dài nhất (Sol 2)

#include <bits/stdc++.h>
using namespace std;

const int maxN = 3e4 + 5;

int n;
int64_t a[maxN];

int64_t d[maxN];

int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#else
    freopen("LIS.inp", "r", stdin);
    freopen("LIS.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int64_t ans = 0;
    for (int i = 1; i <= n; ++i) {
        int64_t left = 1, right = ans;
        int64_t p = -1;

        while (left <= right) {
            int64_t mid = (left + right) / 2;
            if (d[mid] >= a[i])
                p = mid, right = mid - 1;
            else left = mid + 1;
        }

        if (p == -1) d[++ans] = a[i];
        else d[p] = a[i];
    }
    cout << ans << '\n';

    return 0;
}