【題解】ZeroJudge d242: 00481 – What Goes Up

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int a[600000], num, idx, tmp, n[600000];
vector <int> v;
vector <int> ans;
 
int main() {
    cin >> num;
    v.push_back(num);
    n[0] = num;
    a[0] = 1;
    idx++;
    while (cin >> num){
        n[idx] = num;
        if (num > v[v.size()-1]){
            v.push_back(num);
            a[idx] = v.size();
        }
        else {
            *lower_bound(v.begin(), v.end(), num) = num;
            a[idx] = lower_bound(v.begin(), v.end(), num) - v.begin() + 1;
        }
        idx++;
    }
    tmp = v.size();
    cout << tmp << "\n-\n";
    for (int i = idx-1; i >= 0; i--){
        if (a[i] == tmp){
            ans.push_back(n[i]);
            tmp--;
        }
    }
    for (int i = ans.size()-1; i >= 0; i--){
        cout << ans[i] << "\n";
    }
}

# 找出LIS的長度
def LIS():
    v[0] = a[0]
    ranking[0] = 0
    LIS_len = 1
    for i in range(1, N):
        l = 0
        r = LIS_len
        # binary search
        while l < r:
            mid = (l + r) // 2
            if v[mid] >= a[i]:
                r = mid
            else:
                l = mid + 1
        #找出a[i]的ranking
        ranking[i] = l
        v[l] = a[i]
        if l == LIS_len:
            LIS_len += 1
 
    return LIS_len
 
# main program
a = []
while True:
    try:
        a.append(int(input()))
    except:
        break
 
N = len(a)
ranking = [0] * N
v = [0] * N
 
length = LIS()
 
print(f"{length}\n-")
length -= 1
ans = []
for i in range(N-1, -1, -1):
    if (ranking[i] == length):
        ans.append(a[i])
        length -= 1
 
for i in ans[::-1]:
    print(i)