What Goes Up - UVa 481 (PD do Algorithmist)

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
using namespace std;

const int inf =0x3f3f3f3f;
const int MAXN = 100010;

stack<pair<int, int> > dp[MAXN];
int a[MAXN];
int n;

int find(int x) {
    int beg=0, end=n-1;

    while (beg<end) {
        int mid=(beg+end)/2;

        if (dp[mid].top().first>=x) end=mid;
        else beg=mid+1;
    }

    return beg;
}

int main() {
    n=0;
    while (scanf("%d", &a[n++])!=EOF);
    for (int i=0; i<n; i++)
        dp[i].push(make_pair(inf,-1));
    n--;

    dp[1].push(make_pair(a[0],0));
    for (int i=1; i<n; i++) {
        int idx=find(a[i]);
        dp[idx].push(make_pair(a[i],i));
    }

    int sz;
    for (int i=1; i<n+1; i++)
        if (dp[i].top().first==inf) {
            sz=i-1;
            printf("%d\n-\n",i-1);
            break;
        }

    stack<int> s;
    int prev=inf;

    for (sz; sz>0; sz--) {
        while (prev<=dp[sz].top().second)
            dp[sz].pop();
        s.push(dp[sz].top().first);
        prev=dp[sz].top().second;
    }



    while (!s.empty()) {
        printf("%d\n", s.top());
        s.pop();
    }
    return 0;
}