はやし屋

競技プログラミングのメモ きたない

パソコン甲子園2013 予選8問目 (AOJ 0283: Study Session)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0283

二分探索の添え字がずっとバグってて触れてなかった
データ多いからstaticしないとだめです
結局ソースみてしまったのでじぶんでバグらず速く実装したい...

#include<vector>
#include<set>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef multiset < int > :: iterator Itr;

int main(){
  int n , q;scanf("%d%d",&n,&q);
  static vector < int > score(n) , sorted;

  for(int i = 0 ; i < n ; ++i){
    scanf("%d",&score[i]);
    sorted.push_back(score[i]);
  }

  sort(sorted.begin(),sorted.end());

  multiset < int > leader;
  Itr it;
  while(q--){
    char order[11] ;
    int num ;
    scanf("%s %d",order,&num);

    if(*order == 'A'){
      leader.insert(score[num-1]);
    } else if(*order == 'R'){
      it = leader.lower_bound(score[num-1]);
      leader.erase(it);
    } else {

      int lb = 0 , ub = 1 << 28;
      while(lb != ub){
	int mid = (lb+ub)/2;
	int prv = 0 , loss = 0;

	for(it = leader.begin() ; it != leader.end(); ++it){
	  int p = lower_bound(sorted.begin(),sorted.end(),*it - mid) - sorted.begin();
	  loss += max(p - 1 - prv + 1  , 0);
	  prv   = upper_bound(sorted.begin(),sorted.end(),*it) - sorted.begin();
	}

	loss += max(n - 1 - prv + 1 , 0);

	if(loss <= num) ub = mid ;
	else lb = mid + 1 ;
      }
      if(lb != 1 << 28)printf("%d\n",lb);
      else puts("NA");
    }
  }
  return 0;
}