Poj Solution 2823

http://poj.org/problem?id=2823

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1000100], l[1000100], ans[1000100];
int pt[1000100], st[1000100], n, k, m;
bool cmp( int x, int y ) {
    return a[x] < a[y];
}
void calc( ) {
    int i, j, h, sn;    
    for( i=0; i<n; i++ )
        l[i] = i-1, ans[i] = (1<<31), pt[i] = i;    
    l[0] = -10000000;
    sort( pt, pt+n, cmp );
    for( i=0; i<m; i++ ) {
        h = pt[i];
        st[ 0 ] = h;
        sn = 1;
        for( j=l[h]; j>h-k; j=l[j] )
            st[ sn++ ] = j;
        while( sn-- ) {
            l[ st[sn] ] = j;
            if( ans[ st[sn] ] == (1<<31) )
                ans[ st[sn] ] = a[ h ];
        }
    }
}
int main( ) {
    int i;        
    scanf( "%d%d", &n, &k );
    for( i=0; i<n; i++ )
        scanf( "%d", a+i );    
    m = n-k+1;
    calc( );
    for( i=0; i<m; i++ ) {
        printf( "%d", ans[i] );
        if( i != m-1 )printf( " " );
        else printf( "n" );
    }
    for( i=0; i<n; i++ )
        a[i] = -a[i];
    calc( );
    for( i=0; i<m; i++ ) {
        printf( "%d", -ans[i] );
        if( i != m-1 )printf( " " );
        else printf( "n" );
    }
    return 0;
}