2214

//   [My 풀이방법]
//    allocate, release  총 command 수가 30,000 이기 때문에  O(1) 이나  O(logN) 에 각  api 를 처리 해야된다. 
//    allocate 시 가장 적합한 크기의  free area 를 찾아야 하는데  선행탐색으로는  time 아웃 각이다. 
//    만약 크기 순으로 정렬이 되어 있다면  binary search 로 가능하다 이것을  지원하는 구조가 set 구조이다. 
//    set 의 하한값 lower bound : 같거나 큰값중 가장 작은값 을 이용하면 간단하게 해결 된다. 
// 
//    release 시에서  address 순으로 정렬이 되어 있다면 앞/뒷 비교하여 합칠수 있다면 합친다. 
//    이또한 set 구조를 이용하면 쉽게 해결 가능한다. 
//
//    allocate,release 시 같은 set 으로 사용할 수 없기 때문에 각각 만들고 함께 update 해야 된다. 
//    allocate 된 메모리는 hash 형태로 저장하면 O(1) 를 해결 가능하다. 
//    이렇게 하면 전체적으로  O(NlogN) 으로 해결 가능하다. 
//
 
#include <set>
#include <unordered_map>
using namespace std;
 
struct MEM
{
    int addr;
    int size;
 
    bool operator < (const MEM &b)const
    {
        if (size != b.size) return size < b.size;
        return addr < b.addr;
    }
    bool operator > (const MEM &b) const
    {
        if(addr != b.addr)return addr < b.addr;
        return size < b.size;
    }
};
 
set <MEM> fmem;  // size 작은순 + addr   allocate 시 접합한 size 찾을때
set <MEM, greater<MEM>> famem; // addr 작은순 release 시 앞뛰 merge 여부 확인하기 위함.
 
unordered_map <int, int >amem; // alloc mem  addr size 
 
void init(int N) 
{
    fmem.clear();
    famem.clear();
    amem.clear();
    fmem.insert({ 0,N });
    famem.insert({ 0,N });
}
 
int allocate(int mSize) {
 
 
    auto it = fmem.lower_bound({ 0,mSize });
    if (it == fmem.end()) return -1;
    int ret = it->addr;
    amem[it->addr] = mSize;
    if (it->size - mSize > 0)
    {
        fmem.insert({ it->addr + mSize, it->size - mSize });
        famem.insert({ it->addr + mSize, it->size - mSize });
    }
    famem.erase({ it->addr, it->size });
    fmem.erase(it); 
    return ret;
}
 
int release(int mAddr) {
    if (amem.find(mAddr) == amem.end()) return -1;
 
    MEM f;
    int ret;
    f.addr = mAddr;
    ret =f.size = amem[mAddr];
    amem.erase(mAddr); // alloc 에서 삭제 
 
    auto it = famem.insert(f);
    fmem.insert(f);
    // 뒤쪽과 합칠수 있는지 확인하고 합친다.
    auto nx = next(it.first);
    if (nx != famem.end())
    {
         // free  해서 집어넣은 mem와 뒷부분 merge 가능하면
        if (it.first->addr + it.first->size == nx->addr)
        {
            auto tmp =famem.insert({ it.first->addr,it.first->size + nx->size }); // 합쳐 하나로 만들어 넣고
            fmem.insert({ it.first->addr,it.first->size + nx->size });
            fmem.erase({ it.first->addr,it.first->size });
            famem.erase(it.first);  // 기존에 있는 부분 삭제
            fmem.erase({ nx->addr,nx->size });
            famem.erase(nx);
            it = tmp;
        }
    }
    // 앞쪽과 합칠수 있으면 확인하고 합친다. 
    auto pr = prev(it.first);
    if (pr != famem.end())
    {
        if (pr->addr + pr->size == it.first->addr)
        {
            famem.insert({ pr->addr,pr->size + it.first->size }); // 합쳐 하나로 만들어 넣고
            fmem.insert({ pr->addr,pr->size + it.first->size }); 
            fmem.erase({ it.first->addr,it.first->size });
            famem.erase(it.first);  // 기존에 있는 부분 삭제
            fmem.erase({ pr->addr,pr->size });
            famem.erase(pr);
        }
    }
    return ret;
}