Poj Solution 3190

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

#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

int empty[50000];
int use[50000];
int a[50000], b[50000];

typedef pair<int,int> p_i;
p_i p[100000];

int main( ) {
    int i, n, m, ans=0;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%d%d", a+i, b+i );
        p[i*2].first = a[i];
        p[i*2].second = (1<<16) | i;
        p[i*2+1].first = b[i]+1;
        p[i*2+1].second = i;
    }

    sort( p, p+2*n );
    m = 0;

    for( i=0; i<2*n; i++ ) {
        if( p[i].second < (1<<16) )
            empty[m++] = use[ p[i].second ];
        else {
            if( m == 0 )
                use[ p[i].second - (1<<16) ] = ++ans;
            else
                use[ p[i].second - (1<<16) ] = empty[--m];
        }
    }

    printf( "%dn", ans );
    for( i=0; i<n; i++ )
        printf( "%dn", use[i] );

    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 *