Poj Solution 2886

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

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <iterator>
#include <memory.h>

using namespace std;

int tree[500100*4];
int n;

void init( int l, int r, int s ) {
    tree[s] = r-l;
    if( r > l+1 ) {
        int c = (l+r)/2;
        init( l, c, s*2 );
        init( c, r, s*2+1 );
    }
}

void set( int l, int r, int s, int k ) {
    int c = (l+r)/2;
    
    tree[s]--;
    
    if( r == l+1 )
        return;
    else if( k < c )
        set( l, c, s*2, k );
    else
        set( c, r, s*2+1, k );
}

int id;
void find( int l, int r, int s, int count ) {
    int c = (l+r)/2;
    
    if( r == l+1 )
        id = l;
    else if( tree[s*2] >= count )
        find( l, c, s*2, count );
    else
        find( c, r, s*2+1, count-tree[s*2] );
        
}

int p[500100], s[500100];
void clac_point( ) {
    int i, j, h, c;
    
    memset( p, 0, sizeof(p) );
    
    c = 1;
    for( i=2; c<500000; i++ ) {
        if( !p[i] ) {
            c++;
            for( j=i+i; j<=500000; j+=i )
                if( !p[j] )
                    p[j] = i, c++;
        }
    }
    
    s[1] = 1;
    for( i=2; i<=500010; i++ ) {
        if( !p[i] )
            s[i] = 2;
        else {
            h = i;
            for( j=0; h%p[i]==0; h/=p[i], j++ )
                ;
            s[i] = s[ h ]*(j+1);
        }
    }
}

char name[500010][12];
int num[500010];
int k;
bool input() {
    int i;
    if( scanf( "%d%d", &n, &k ) != 2 )
        return false;
    for( i=0; i<n; i++ ) 
        scanf( "%s%d", name[i], num+i );
    return true;
}

int main( ) {
    int i, m, best, k, j;
    
    clac_point( );
    
    while( input() ) {
        best = 1;
        for( i=2; i<=n; i++ )
            if( s[ best ] < s[ i ] )
                best = i;
                
        init( 0, n, 1 );
        k = ::k-1;
        j = ::k;
        m = n;
        for( i=1; i<best; i++ ) {
            set( 0, n, 1, k );
            m--;
            if( num[k] > 0 )
                j = (j-1+num[k]-1)%m+1;
            else {
                j = (j+num[k]-1)%m;
                if( j < 0 ) j+=m;
                j++;
            }
            find( 0, n, 1, j );
            k = id;
//            printf( "%s %dn", name[k], j );
        }
        
        printf( "%s %dn", name[k], s[best] );
    }
    return 0;
}