Untitled

 avatar
unknown
plain_text
5 months ago
1.8 kB
3
Indexable
#include <set>
#include <unordered_map>
typedef std::pair<int, int> pii;
using namespace std;

struct cmp{
	bool operator()(pii a, pii b) {
		if(a.second - a.first == b.second - b.first) return a.first < b.first;
		return a.second - a.first > b.second - b.first;
	}
};
int n;
set<pii,cmp>space;
set<pii>se;
unordered_map<int, int>mp;
void init(int N) {
	n = N;
	space.clear();
	se.clear();
	mp.clear();

	space.insert(make_pair(0, n-1));
	se.insert(make_pair(0, n-1));
}
int build(int mLenght) {
	int res = -1;
	auto land = space.begin();
	int st = land->first;
	int en = land->second;	
	if(en - st  + 1 < mLenght) return -1;

	space.erase(land);
	se.erase(land);

	res = st + (en - st) / 2;
	space.insert(make_pair(st, res-1));
	space.insert(make_pair(res + mLenght, en));

	se.insert(make_pair(st, res-1));
	se.insert(make_pair(res + mLenght, en));

	mp[res] = mLenght;
	return res;
}
int demolish(int mAddr) {
	if(mp.find(mAddr) != mp.end()) {
		int len = mp[mAddr];
	int newst, newen;
	mp.erase(len);
	int st = mAddr;
	int en = st + len - 1;

	auto pre = space.lower_bound(make_pair(st, en));
	pre--;
	if(st == 0) newst = 0;
	if(pre->second + 1 == st) newst = pre->first;
	else if(pre->second + 1 != st) newst = st;

	auto nex = space.upper_bound(make_pair(st, en));
	if(en == n-1) newen = n-1;
	if(nex->first - 1 == en) newen = nex->second;
	else if(nex->first - 1 != en) newen = en;

	space.erase(make_pair(pre->first, pre->second));
	space.erase(make_pair(nex->first, nex->second));

	se.erase(make_pair(pre->first, pre->second));
	se.erase(make_pair(nex->first, nex->second));

	space.insert(make_pair(st, en));
	space.insert(make_pair(st, en));

	return len;
	}
	else return -1;
}
Editor is loading...
Leave a Comment