2013年8月10日

UVa 481 - What Goes Up

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
vector<vector<P> > ans;

void print(vector<vector<P> > & v, int index, int last) {
  if (index == -1) {
    return;
  }
  for (int i = v[index].size() - 1; i >= 0; i--) {
    if (v[index][i].second < last) {
      print(v, index - 1, v[index][i].second);
      printf("%d\n", v[index][i].first);
      return;
    }
  }
}

int N, num[1000000];

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    num[N++] = n;
  }
  vector<int> v;
  v.push_back(num[0]);
  vector<P> tmp;
  tmp.PB(MP(num[0], 0));
  ans.PB(tmp);
  for (int i = 1; i < N; i++) {
    if (num[i] > v.back()) {
      v.push_back(num[i]);
      tmp.clear();
      tmp.PB(MP(num[i], i));
      ans.PB(tmp);
    } else {
      vector<int>::iterator it = lower_bound(v.begin(), v.end(), num[i]);
      *it = num[i];
      int index = it - v.begin();
      ans[index].PB(MP(*it, i));
    }
  }
  printf("%d\n-\n", ans.size());
  print(ans, ans.size() - 1, 2e9);
  return 0;
}

沒有留言:

張貼留言