What Goes Up - UVa 481 (Segtree)

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

const int MAXN = 100010;
int tree[4*MAXN];
int n;
int a[MAXN];
int ord[MAXN];
int dp[MAXN];

int find(int x) {
    for (int beg=0, end=n-1; beg<=end; ) {
        int mid=(beg+end)/2;

        if (ord[mid]==x) return mid;

        if (ord[mid]<x) beg=mid+1;
        else end=mid-1;
    }

    return -1;
}

void update(int root, int l, int r, int pos, int val) {
    if (l==r) {
        tree[root]=val;
        return;
    }

    int mid=(l+r)/2;

    if (pos<=mid) update(2*root+1,l,mid,pos,val);
    else update(2*root+2,mid+1,r,pos,val);

    tree[root]=max(tree[2*root+1],tree[2*root+2]);
}

int query(int root, int l, int r, int ql, int qr) {
    if (ql<=l && qr>=r)
        return tree[root];

    int mid=(l+r)/2;

    int maxS=0;
    if (ql<=mid) maxS=max(maxS,query(2*root+1,l,mid,ql,min(qr,mid)));
    if (qr>mid) maxS=max(maxS,query(2*root+2,mid+1,r,max(ql,mid+1),qr));

    return maxS;
}

int main() {
    n=0;
    while (scanf("%d", &a[n++])!=EOF);
    memset(tree,0,sizeof(tree));

    for (int i=0; i<n; i++)
        ord[i]=a[i];
    sort(ord,ord+n);

    update(0,0,n-1,find(a[0]),1);
    dp[0]=1;

    for (int i=1; i<n; i++) {
        int idx=find(a[i]);
        int d=0;

        if (idx) d=query(0,0,n-1,0,idx-1);
        d+=1;

        update(0,0,n-1,idx,d);
        dp[i]=d;
    }

    int ans=0, prev;
    stack<int> s;
    for (int i=0; i<n; i++)
        if (ans<=dp[i]) ans=dp[i], prev=i;

    printf("%d\n-\n", ans);
    s.push(prev);

    for (int i=prev-1; i>=0; i--)
        if (dp[i]+1==dp[prev] && a[i]<a[prev]) {
            s.push(i);
            prev=i;
        }

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