2339

#if 1
//
//  Hash  + PQ  
//
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
#define rint register int
using pii = pair<int, int>;
 
struct File
{
    int id;
    int sz; // size 
    vector<pii> assign;  // 할당 리스트 {from, to }
    File *init(int _id, int _sz) {
        id = _id, sz = _sz;
        assign.clear();
        return this;
    }
    void st_assign(int pos, int size) // 저장소 정보 
    {
        assign.push_back({ pos,size });
    }
    void remove()
    {
        sz = 0;
        assign.clear();
    }
}F[15000];
int f_idx;
int file_tot_size;
 
unordered_map< int, File*> Hash; // file hash 
priority_queue<pii, vector<pii>, greater<pii> > pq_st; //  file storage 저장소 
 
void init(int N) {
    pq_st = {};
    file_tot_size = N;
    Hash.clear();
    //s_assign.clear();
    f_idx = 0;
    pq_st.push({ 1,N }); // start , size  end = first + N -1; 
}
 
int add(int mId, int mSize) {
    if (mSize > file_tot_size) return -1; // 남아 있는 전체 저장소 크기 확인 
    file_tot_size -= mSize;
    File *fp = F[++f_idx].init(f_idx, mSize); // F struct 할당 
    Hash[mId] = fp; //hash 생성 
    // 저장소에서 위치가 빠른 순으로 여유 공간을 차례로 가져와 요구하는 size 만큼 할당하고 정보를 저장한다. 
    while (mSize > 0) {
        auto it = pq_st.top(); pq_st.pop();
        while (!pq_st.empty() &&it.first + it.second == pq_st.top().first)
        {
            it.second += pq_st.top().second;
            pq_st.pop();    
        }
        int assign_size = min(it.second, mSize);
        it.second -= assign_size; //남은양
        mSize -= assign_size; // 남은 필요양 
        fp->st_assign(it.first, assign_size);
        if (it.second > 0) {
            it.first += assign_size;
            pq_st.push(it);
        }
    }
    return fp->assign.begin()->first;
}
 
int remove(int mId) {
     
    File *fp = Hash[mId];
    int cnt = fp->assign.size();
    for (auto it : fp->assign){
        pq_st.push(it); // 저장소로 반납
    }
    file_tot_size += fp->sz; // 전체 여유 공간 반납
    fp->remove(); // file 정보 관련 정리 
    Hash[mId] = 0; // 해쉬 삭제 
    return cnt;
}
 
int count(int mStart, int mEnd) {
    rint cnt = 0;
    // 현재까지 add 된 file 모두를 확인한다. 
    for(rint i =0;i <= f_idx;++i)
    {
        if (F[i].sz== 0) continue; // 삭제된 file 은 제외 
        for (auto j =0;j < F[i].assign.size(); ++j)
        {
            int s =  F[i].assign[j].first, e = F[i].assign[j].first + F[i].assign[j].second- 1;
            if (!(s > mEnd || e < mStart)) { //  조각중 하나라도 Start,End에  포함된것이 있으면 
                cnt++; //  count 증가 시키고 
                break; // 종료 다음 file 확인 (중요) 
            }
        }
    }
    return cnt;
}
#endif // 10