Untitled
unknown
plain_text
5 months ago
1.9 kB
4
Indexable
#include <set> #include <unordered_map> using namespace std; typedef pair<int, int> pii; struct cmp { bool operator()(pii a, pii b) const { if (a.second - a.first != b.second - b.first) return (a.second - a.first) > (b.second - b.first); // Ưu tiên đoạn dài hơn return a.first < b.first; // Nếu độ dài bằng nhau, ưu tiên vị trí nhỏ hơn } }; 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({0, n - 1}); se.insert({0, n - 1}); } int build(int mLength) { if (space.empty()) return -1; int res = -1; auto land = space.begin(); int st = land->first; int en = land->second; if (en - st + 1 < mLength) return -1; space.erase(land); se.erase({st, en}); res = st + (en - st) / 2; if (res - 1 >= st) { space.insert({st, res - 1}); se.insert({st, res - 1}); } if (res + mLength <= en) { space.insert({res + mLength, en}); se.insert({res + mLength, en}); } mp[res] = mLength; return res; } int demolish(int mAddr) { if (mp.find(mAddr) == mp.end()) return -1; int len = mp[mAddr]; mp.erase(mAddr); int st = mAddr; int en = st + len - 1; auto pre = space.lower_bound({st, en}); if (pre != space.begin()) pre--; auto nex = space.upper_bound({st, en}); int newst = st, newen = en; if (pre != space.end() && pre->second + 1 == st) { newst = pre->first; space.erase(pre); se.erase(*pre); } if (nex != space.end() && nex->first == en + 1) { newen = nex->second; space.erase(nex); se.erase(*nex); } space.insert({newst, newen}); se.insert({newst, newen}); return len; }
Editor is loading...
Leave a Comment