1819.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1819 on 2006-04-22 at 16:22:29 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int WM = 1 << 18;
const int LMT = 1 << 19;

class TreeArray {
private:
	int cnt[LMT], emn[LMT];
	int lowBit(int t) { return t&(-t); }
	int sum(int);
public:
	void clear();
	void insert(int, int);
	int find(int);
	int del(int, int);
};
void TreeArray::clear() {
	memset(cnt, 0, sizeof(cnt));
	memset(emn, 0, sizeof(emn)); 
}
int TreeArray::sum(int k) {
	int total = 0;
	for(; k > 0; k -= lowBit(k)) total += emn[k];
	return total;
}
void TreeArray::insert(int k, int n) {
	cnt[k] += n;
	for(; k < LMT; k += lowBit(k)) emn[k] += n;
}
int TreeArray::find(int k) {
	int b = 0, e = LMT-1;
	while(b != e) {
		int mid = (b + e) / 2;
		if(sum(mid) < k) b = mid+1;
		else e = mid;
	}
	return b;
}
int TreeArray::del(int b, int e) {
	int i, lev = 0;
	for(i = b; i < e; i++) {
		lev += cnt[i];
		insert(i, -cnt[i]);
	}
	return lev;
}

TreeArray list;

int main()
{
	int t, T, low;

	while(scanf("%d %d", &T, &low) != EOF) {
		int d = -WM, leave = 0, en = 0;
		list.clear();
		for(t = 0; t < T; t++) {
			char o; int k; scanf("\n%c %d", &o, &k);
			if(o == 'I') {
				if(k < low) continue;
				list.insert(k-d, 1); en++;
			} else if(o == 'A') d += k;
			else if(o == 'S') {
				int prev = low - d;
				d -= k;
				int de = list.del(prev, low-d);
				en -= de; leave += de;
			} else {
				if(k > en) printf("-1\n");
				else printf("%d\n", list.find(en-k+1)+d);
			}
		}
		printf("%d\n", leave);
	}
	
	return 0;
}