BOJ 14003번 가장 긴 증가하는 부분수열5

BOJ : https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

4번 문제와 다른점은 배열의 개수와, 표현범위가 10억이라는 점이다.

4번 : https://junho0956.tistory.com/9?category=825556

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
 
int lis, n;
long long arr[1000001];
long long Lis[1000001];
vector<pair<int, long long> > pii;
stack<long long> s;
 
int lower_bound(int start, int end, long long key)
{
    int mid;
    while (end - start > 0)
    {
        mid = (start + end) / 2;
 
        if (Lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i)
        scanf("%lld", &arr[i]);
 
    Lis[0] = arr[0];
    pii.push_back(make_pair(0, Lis[0]));
 
    for (int i = 1; i < n; i++) {
        if (Lis[lis] < arr[i])
        {
            Lis[lis + 1] = arr[i];
            lis++;
 
            pii.push_back(make_pair(lis, arr[i]));
        }
        else
        {
            int ans = lower_bound(0, lis, arr[i]);
            Lis[ans - 1] = arr[i];
 
            pii.push_back(make_pair(ans - 1, arr[i]));
        }
    }
 
    printf("%d\n", lis + 1);
 
    for (int i = pii.size(); i >= 0; i--) {
        if (pii[i - 1].first == lis) {
            s.push(pii[i - 1].second);
            lis--;
        }
        if (lis == -1) break;
    }
 
    while (!s.empty()) {
        printf("%lld ", s.top()), s.pop();
    }
 
    return 0;
}