PKU 2886 Who Gets the Most Candies?

削除のある配列のi番目をlogでわかるようにする。
Segment Treeの典型。IOI2012のpracticeでも本番でもこんなの書いた覚えがある。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[500010][16];
int c[500010];
int v[500010];
int segtree[1048576];
void add(int a,int b){
	a+=(1<<19);
	while(a){
		segtree[a]+=b;
		a/=2;
	}
}
int find(int a){
	a++;
	int L=0;
	int R=(1<<19);
	int u=1;
	while(L+1<R){
		int M=(L+R)/2;
		if(a>segtree[u*2]){
			a-=segtree[u*2];
			u=u*2+1;
			L=M;
		}else{
			R=M;
			u=u*2;
		}
	}
	return L;
}
int main(){
	int a,b;
	for(int i=1;i<500010;i++){
		for(int j=i;j<500010;j+=i)v[j]++;
	}
	while(~scanf("%d%d",&a,&b)){
		for(int i=0;i<(1<<20);i++)segtree[i]=0;
		for(int i=0;i<a;i++)add(i,1);
		b--;
		for(int i=0;i<a;i++){
			scanf("%s%d",str[i],c+i);
			if(c[i]>0)c[i]--;
		}
		int now=0;
		int ret=0;
		int at=b;
		int at2=b;
		for(int i=0;i<a;i++){
		//	printf("%s %d %d\n",str[at],at,at2);
			if(now<v[i+1]){
				ret=at;
				now=v[i+1];
			}
			add(at,-1);
			if(i==a-1)break;
			at2=(at2+c[at])%segtree[1];
			if(at2<0)at2+=segtree[1];
			at=find(at2);
		}
		printf("%s %d\n",str[ret],now);
	}
}