2339
unknown
plain_text
7 months ago
3.0 kB
2
Indexable
Never
#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
Leave a Comment