Untitled
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