Codeforces #165 div1-A,div2-C Magical Boxes

http://www.codeforces.com/contest/269/problem/A

問題概要

N種類の大きさの箱がある。
i番目の箱の大きさは2^k(i)で、a(i)個ある。

新しく2^pの大きさの箱を作って、それにすべての元の箱を詰めたい。
ある箱には、それより小さい大きさの箱を、半分の大きさなら4個、1/4の大きさなら16個、というように詰めることができ、入れ子状に詰めることも出来る。
ある箱に、サイズの異なる箱を詰めることも出来る(半分の大きさの箱1つ、1/4の大きさの箱12個 のように)
pの最小値を求めよ

N<=10^5 a,k<=10^9

方針

ある箱が入れ子状に詰められているとしても、
サイズごとに、互いに干渉しない箱を別々に新しい箱に詰めている、とみなすことができる
なので、それぞれのサイズについて、箱を詰めることが出来る最小のサイズを求め、maxを取る。
サイズ2^k(i)のa(i)個の箱が詰まる最小のサイズは、2^(p-k(i))>=a(i)を満たす最小のp
ただし、p>k(i)

O(N*log a)

int n;
pair<int,int> box[100005];
int main(){
	cin>>n;

	int res=0;
	for(int i=0;i<n;++i){
		scanf("%d%d",&box[i].first,&box[i].second);
		
		if(box[i].second==1) res=max(res,box[i].first+1);
		else{
			while(box[i].second>1){
				box[i].second=(box[i].second+3)/4;
				++box[i].first;
			}
			res=max(res,box[i].first);
		}
	}
	printf("%d\n",res);

	return 0;
}