Untitled

 avatar
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