AOJ0283 勉強会

解法

---

2分探索使ってほげると良い。
multisetとかmapとか色々使ったけどやっぱりvectorが実行時間が短かった。

ソース

---

#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
using namespace std;
 
#define INF ( 1 << 30 )
typedef pair < int , int > Pi;
 
int main()
{
  int N, Q;
  int stmp[1000000], comp[1000000], a;
  char buff[1024];
  scanf( "%d %d", &N, &Q);
  for(int i = 0 ; i < N ; i++ ){
    scanf( "%d", &stmp[i]);
    comp[i] = stmp[i];
  }
  sort( comp, comp + N);
 
  vector< int > sym;
  while(Q--){
    scanf("%s %d", buff, &a);
    if(*buff == 'A'){ //ADD
 
      sym.push_back(stmp[a - 1]);
      sort( sym.begin(), sym.end());
 
    } else if(*buff == 'R'){ //REMOVE
 
      sym.erase( lower_bound( sym.begin(), sym.end(), stmp[a - 1]));
 
    } else { //CHECK
 
      int left = 0, right = INF;
      while(left != right){
        int center = ( left + right ) / 2;
        int pre = 0, BAN = 0;
        for(int i = 0 ; i < sym.size() ; i++ ){
          int p = distance( comp,lower_bound( comp, comp + N, sym[i] - center));
          BAN += max( p - pre, 0);
          pre = distance( comp, upper_bound( comp, comp + N, sym[i]));
        }
        BAN += max( N - pre, 0);
        if(BAN <= a) right = center;
        else left = center + 1;
      }
      if( left != INF) printf("%d\n", left);
      else puts("NA");
 
    }
  }
  return false;
}