Codeforces Round #135 (Div. 2) E : Parking Lot

問題概要

1~N(N<2e5)の座席があり、最初は全部空席である。新たに客が来たとき、最も近い位置にある非空な席までの距離が最も遠くなるような位置に座る。複数あるときはその中で最も左に座る。各客が座る座席を出力する問題。

解法

max-heapに区間を突っ込んでいけば良い。ただし、heap内の区間を削除したりすることがある。pairing heapなどのheapを使ってもよいが、ポインタを利用して直接中身をいじることでも対応できる。

acceptされたコード

#include <cstdio>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int MAX_N = int(2e5);
const int MAX_Q = int(2e5);

int N, Q;
int ts[MAX_Q], ids[MAX_Q];
bool isFilled[MAX_N];

struct Range {
	int from, to, dist;
	bool isValid;

	Range(){}
	Range(int from, int to):
		from(from), to(to), isValid(true)
	{
		if (from == 0) {
			dist = to - 1;
		}
		else if (to == N) {
			dist = to - from - 1;
		}
		else {
			dist = (to - from - 1) >> 1;
		}
	}
};

Range rs__[MAX_N*5];
int rr__;

Range *getNewRange(int from, int to) {
	rs__[rr__] = Range(from, to);
	return &rs__[rr__++];
}

bool operator< (const Range& lhs, const Range& rhs) {
	if ( lhs.from != rhs.from ) return lhs.from < rhs.from;
	return lhs.to < rhs.to;
}


struct Comp {
	bool operator() (const Range *lhs, const Range *rhs) {
		if (lhs->dist != rhs->dist) {
			return lhs->dist < rhs->dist;
		}
		else {
			return lhs->from > rhs->from;
		}
	}
};

priority_queue<Range*, vector<Range*>, Comp> que;
map< pair<int,int>, Range* > dict;
set< pair<int,int> > valids;
set< pair<int,int> >::iterator prev, post;
map<int, int> idToPosition;

void init() {
	scanf("%d%d", &N, &Q);
	for (int i = 0; i < Q; ++i) {
		scanf("%d%d", ts+i, ids+i);
	}
}

void addRange(Range *nr) {
	dict[make_pair(nr->from, nr->to)] = nr;
	valids.insert(make_pair(nr->from, nr->to));
	que.push(nr);
}

void removeRange(Range *nr) {
	pair<int,int> rp = make_pair(nr->from, nr->to);
	dict[rp]->isValid = false;
	valids.erase(rp);
}

void solve() {

	
	{
		Range *r = new Range(0, N);
		valids.insert(make_pair(0, N));
		dict[make_pair(0, N)] = r;
		que.push(r);
	}

	for (int i = 0; i < Q; ++i) {
		const int id = ids[i];
		if (ts[i] == 1) { 
			for (;!que.empty() && !que.top()->isValid; que.pop()) ;
			Range *r = que.top(); que.pop();

			int pos = -1;
			if (r->from == 0) {
				pos = r->from;
			}
			else if (r->to == N) {
				pos = r->to - 1;
			}
			else {
				pos = r->from + r->dist;
			}
			idToPosition[id] = pos;
			isFilled[pos] = true;
			printf("%d\n", pos + 1);

			valids.erase(make_pair(r->from, r->to));
			if (r->to - r->from == 1) {
				continue;
			}
			if (r->from == 0) {
				addRange(getNewRange(r->from+1, r->to));
			}
			else if (r->to == N) {
				addRange(getNewRange(r->from, r->to-1));
			}
			else {
				Range *nrl = getNewRange(r->from, pos);
				if (nrl->to - nrl->from >= 1) {
					addRange(nrl);
				}
				Range *nrr = getNewRange(pos+1, r->to);
				if (nrr->to - nrr->from >= 1) {
					addRange(nrr);
				}
			}
		}
		else { 
			const int pos = idToPosition[id];
			isFilled[pos] = false;
			Range *nr = 0;
			if (0 < pos && pos < N - 1 && !isFilled[pos - 1] && !isFilled[pos + 1]) {
				post = valids.lower_bound(make_pair(pos+1, -1));
				prev = post;
				advance(prev, -1);
				removeRange(dict[*prev]);
				removeRange(dict[*post]);
				nr = getNewRange(prev->first, post->second);
				addRange(nr);
			}
			else if (pos < N - 1 && !isFilled[pos + 1]) {
				post = valids.lower_bound(make_pair(pos+1, -1));
				nr = getNewRange(pos, post->second);
				removeRange(dict[*post]);
				addRange(nr);
			}
			else if (pos > 0 && !isFilled[pos - 1]) {
				prev = valids.lower_bound(make_pair(pos, -1));
				advance(prev, -1);
				nr = getNewRange(prev->first, pos+1);
				removeRange(dict[*prev]);
				addRange(nr);
			}
			else {
				nr = getNewRange(pos, pos + 1);
				addRange(nr);
			}
		}
	}
}

int main() {
	init();
	solve();

	return 0;
}