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); }