Poj Solution 3044

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

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

int id[50000];
int h[50000];
bool sign[50000];
int temp[2][51000];
int *next = &temp[0][1];
int *pri = &temp[1][1];

bool cmp( int a, int b ) {
    return h[a] > h[b];
}

int main() {
    int n, i, j, count;
    scanf( "%d%*d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%*d%d", h+i );
        id[i] = i;
        next[i] = i+1;
        pri[i] = i-1;
        sign[i] = true;
    }

    std::sort( id, id+n, cmp );

    count = 0;
    for( i=0; i<n && h[ id[i] ]; i++ ) 
    if( sign[id[i]] ){
        j = id[i];
        count ++;
        if( pri[j] >= 0 && next[j] < n && h[ pri[j] ] == h[ next[j] ] ) {
            sign[ next[j] ] = false;
            next[ pri[j] ] = next[ next[j] ];
            pri[ next[next[j]] ] = pri[j];
        }
        else {
            next[ pri[j] ] = next[j];
            pri[ next[j] ] = pri[j];
        }
    }

    printf( "%dn", count );
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *