poj 2886Who Gets the Most Candies?

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<memory.h>

int seg_tree[500010<<2];

void build_tree(int l,int r,int id);

void push_tree_up(int id);

void update_tree(int value,int l,int r,int id);

int f[500010];

void get_f();

int num[500010],h;

char str[500010][10];

int cur_n,cur_i,next_i,ans,ans1;

int main()

{

    int n,k,i,j,cur,temp;

    //freopen("d:\\2.txt","r",stdin);

    //freopen("d:\\3.txt","w",stdout);

    memset(f,0,sizeof(f));

    get_f();

    while(scanf("%d%d%*c",&n,&k)!=EOF)

    {

        for(i=1;i<=n;i++)

            scanf("%s%d",str[i],num+i);

        cur_n=n;

        cur_i=n;

        next_i=k;

        build_tree(1,n,1);

        ans=0;

        ans1=1;

        h=1;

        for(i=1;i<=n;i++)

        {

        //  printf("cur_i=%d next_i=%d",cur_i,next_i);

                  if(next_i>=0)

                      cur_i--;

                  cur=(cur_i+next_i%cur_n+cur_n)%cur_n;

              //   printf(" cur=%d
",cur);

            update_tree(cur+1,1,n,1);

            cur_i=cur;

            h++;





        }

        printf("%s %d
",str[ans1],ans);



    }



}

void build_tree(int l,int r,int id)

{

    if(l==r)

    {

        seg_tree[id]=1;

        return ;

    }

    int mid=(l+r)>>1;

    build_tree(l,mid,id<<1);

    build_tree(mid+1,r,id<<1|1);

    push_tree_up(id);

}

void push_tree_up(int id)

{

    seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1];

}

void update_tree(int value,int l,int r,int id)

{

    if(l==r)

    {

        seg_tree[id]--;

    // printf("tree[id]=%d",seg_tree[id]);

    //    printf("l=%d
",l);

            next_i=num[l];

        cur_n--;

        if(ans<f[h])

        {



        ans=f[h];

        ans1=l;

        }

        return ;

    }

    int mid=l+r>>1;

    if(value<=seg_tree[id<<1])

    {

        update_tree(value,l,mid,id<<1);

    }

    else

    {

        update_tree(value-seg_tree[id<<1],mid+1,r,id<<1|1);

    }

    push_tree_up(id);

}

void get_f()

{



    int i,j;

    for(i=1;i<=500000;i++)

    for(j=1;i*j<=500000;j++)

    {

        f[i*j]++;

    }

}