uva481 - lis in nlogk time

uva481.cpp

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }


const int maxn=(int)4e5+5;


void lisFast(vector<int>& a, int& ans, vector<int>& res) {
  int n = a.size();
  // L[i] = smallest elem to be in lis of length i
  vector<int> L;
  vector<int> L_id(n);
  vector<int> P(n);

  int lis = 0, lis_end = 0;
  for (int i = 0; i < n; ++i) {
    auto pos = lower_bound(L.begin(), L.end(), a[i]);
    if (pos == L.end()) {
      L.push_back(a[i]);
      pos = --L.end();
    } else {
      *pos = a[i];
    }
    int idx = pos - L.begin();
    L_id[idx] = i;
    
    if (idx == 0) P[i] = -1; else P[i] = L_id[idx-1];
    
    if (idx + 1 > lis) {
      lis = idx + 1;
      lis_end = i;
    }
  }

  ans = lis;
  int x = lis_end;
  stack<int> s;
  for (; P[x]>=0; x=P[x]) s.push(a[x]);
  res.push_back(a[x]);
  for (; !s.empty(); s.pop()) res.push_back(s.top());
}

void lisSlow(vector<int>& a, int& ans, vector<int>& res) {
  int n = a.size();
  vector<int> prev(n,-1);
  vector<int> dp(n,1);
  for (int i=1; i<n; i++) {
    for (int j=i-1; j>=0; j--) {
      if (a[j] < a[i]) {
	if (dp[j] + 1 > dp[i]) {
	  dp[i] = dp[j] + 1;
	  prev[i] = j;
	}
      }
    }
  }
  int p = n-1;
  for (int i=n-1; i>=0; i--) {
    if (dp[i] > dp[p]) {
      p = i;
    }
  }

  ans = dp[p];
  while (p != -1) {
    res.push_back(a[p]);
    p = prev[p];
  }
  reverse(res.begin(), res.end());
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  //cout << fixed << setprecision(6);
  vector<int> a;
  int x;
  while(cin>>x) a.push_back(x);

  int n;
  vector<int> res;

  lisFast(a,n,res);
  cout<<n<<endl;
  cout<<"-"<<endl;
  for (auto x: res) cout<<x<<endl;

  return 0;
}