AOJ 0283 - Study Session

問題文

勉強会

解法

予選のときにひどいソースを出してバグったので書きなおした.
multiset を使って, リーダーについて見れる生徒をiterate すると良い. $O(Q leadernum \log^2 leadernum \log D)$ くらい.$D$ は二分探索の幅.

コード

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <climits>

using namespace std;

typedef long long lint;

const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 1001001001;
const lint INFLL = 1001001001001001001ll;

#define zclear(a) memset((a), 0, sizeof(a))
#define mclear(a) memset((a), -1, sizeof(a))

#define show(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int a[1000000];
vector<int> cmp;

int main()
{
	int N, Q;
	
	scanf("%d %d", &N, &Q);
	
	for (int i = 0; i < N; i++){
		scanf("%d", a + i);
		cmp.push_back(a[i]);
	}
	
	sort(cmp.begin(), cmp.end());
	
	multiset<int> ms;
	multiset<int>::iterator it;
	for (int i = 0; i < Q; i++){
		char q[1024];
		int arg;
		scanf("%s %d", q, &arg);
		
		if (q[0] == 'A'){
			ms.insert(a[--arg]);
		}
		else if (q[0] == 'R'){
			it = ms.lower_bound(a[--arg]);
			ms.erase(it);
		}
		else {
			int lo = 0, hi = 1000000001;
			
			while (lo != hi){
				int mid = lo + hi >> 1;
				int prev = 0;
				int fail = 0;
				
				for (it = ms.begin(); it != ms.end(); it++){
					int pos = lower_bound(cmp.begin(), cmp.end(), *it - mid) - cmp.begin();
					fail += max(pos - 1 - prev + 1, 0);
					prev = upper_bound(cmp.begin(), cmp.end(), *it) - cmp.begin();
				}
				fail += max(N - 1 - prev + 1, 0);
				if (fail <= arg) hi = mid;
				else lo = mid + 1;
			}
			if (lo != 1000000001) printf("%d\n", lo);
			else printf("NA\n");
		}
	}
	
	return (0);
}