Indeedなう（予選A） : C - 説明会

ABC相当の問題なのか、割と典型。
http://indeednow-quala.contest.atcoder.jp/tasks/indeednow_2015_quala_3

問題

N人の参加者の得点S[i]が与えられる。

ここでQ個のクエリK[j]が与えられる。
各クエリに対し、正であるx点以上の得点者がK[j]人以下となるような最小のxを答えよ。

解法

まず累積和を取りx点以上の得点者をO(1)で求められるようにする。
あとは二分探索で得点者がK[j]人以下となる最小のxを求めればよい。

int N,Q;
ll S[1<<21],K[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(x) S[x]++;
	}
	
	for(i=1<<20;i>=0;i--) S[i]+=S[i+1];
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		
		int ret=(1<<20)-1;
		for(j=19;j>=0;j--) if(S[ret-(1<<j)]<=x) ret-=1<<j;
		cout<<ret<<endl;
	}
}

まとめ

途中細かいミスでタイムロスしたのが残念。