//package day23;
import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;
class UserSolution {
class Memory{
int start,end,size;
boolean isEmpty;
Memory(int startt,int end, int size){
this.start = startt;
this.end = end;
this.size = size;
}
void updateValue(int startt,int end, int size){
this.start = startt;
this.end = end;
this.size = size;
}
}
void addMemEmpty(Memory m){
emptyMem.add(m);
emptyMemory.put(m.start, m);
emptyMemory.put(m.end, m);
}
void removeMem(Memory m){
if (m != null) {
emptyMem.remove(m);
emptyMemory.remove(m.start);
emptyMemory.remove(m.end);
}
}
Comparator<Memory> com = new Comparator<Memory>() {
public int compare(Memory m1 , Memory m2) {
return m2.size == m1.size ? m1.start - m2.start : m1.size - m2.size;
}
};
int n;
TreeSet<Memory> emptyMem = new TreeSet<>(com);
HashMap<Integer, Memory> emptyMemory = new HashMap<Integer, Memory>();
HashMap<Integer, Memory> MemoryAllocated = new HashMap<Integer, Memory>();
public void init(int N) {
n = N;
emptyMem = new TreeSet<>(com);
emptyMemory = new HashMap<Integer, Memory>();
MemoryAllocated = new HashMap<Integer, Memory>();
addMemEmpty(new Memory(0, n-1,n));
}
public int allocate(int mSize) {
Memory newAllocate = new Memory(0, 0, mSize);
Memory empty = emptyMem.ceiling(newAllocate);
// System.out.println("******" + empty.size);
removeMem(empty);
if (empty != null) {
newAllocate = new Memory(empty.start, empty.start + mSize- 1, mSize);
MemoryAllocated.put(newAllocate.start, newAllocate);
// System.out.println("******" );
if (empty.size > mSize) {
Memory newEmpty = new Memory(empty.start+mSize, empty.end, empty.size-mSize);
addMemEmpty(newEmpty);
}
// System.out.println("******" + newAllocate.start);
return newAllocate.start;
}
return -1;
}
public int release(int mAddr) {
int res = -1;
Memory m = MemoryAllocated.get(mAddr);
if (m != null) {
MemoryAllocated.remove(m.start);
res = m.size;
Memory m1 = emptyMemory.get(m.start-1);
if (m1 != null) {
removeMem(m1);
m.updateValue(m1.start, m.end, m1.size+m.size);
}
Memory m2 = emptyMemory.get(m.end+1);
if (m2 != null) {
removeMem(m2);
m.updateValue(m.start, m2.end, m2.size+m.size);
}
addMemEmpty(m);
}
// System.out.println("******" + res);
return res;
}
}
////////////////////////
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> row[700];
vector<int> col[10000];
int mRow;
int mCol;
int vis[700][10000];
int cnt=0;
queue<pair<int,int>> q;
void init(int R, int C, int M, int mStructureR[30000], int mStructureC[30000])
{
for (int i = 0; i < R; i++) {
row[i] = { -1, C };
}
for (int i = 0; i < C; i++) {
col[i] = { -1, R };
}
for (int i = 0; i < M; i++) {
row[mStructureR[i]].push_back(mStructureC[i]);
col[mStructureC[i]].push_back(mStructureR[i]);
}
for (int i = 0; i < R; i++)
sort(row[i].begin(), row[i].end());
for (int i = 0; i < C; i++)
sort(col[i].begin(), col[i].end());
mRow = R;
mCol = C;
}
int minDamage(int mStartR, int mStartC, int mEndR, int mEndC)
{
int damage = 0;
cnt++;
if(mStartR==mEndR && mStartC==mEndC) return damage;
q = {};
q.push({mStartR,mStartC});
vis[mStartR][mStartC] = cnt;
while(!q.empty())
{
int sz = q.size();
for(int i=0;i<sz;i++)
{
auto temp = q.front();
int x = temp.first;
int y = temp.second;
auto nextCol = lower_bound(row[x].begin(),row[x].end(),y);
auto prevCol = nextCol - 1;
if(x == mEndR && *prevCol < mEndC && *nextCol > mEndC)
return damage;
auto nextRow = lower_bound(col[y].begin(),col[y].end(),x);
auto prevRow = nextRow - 1;
if(y == mEndC && *prevRow < mEndR && *nextRow > mEndR)
return damage;
if (*nextCol != mCol && vis[x][*nextCol - 1] != cnt) { // down
q.push({ x, *nextCol - 1 });
vis[x][*nextCol - 1] = cnt;
}
if (*prevCol != -1 && vis[x][*prevCol + 1] != cnt) { // up
q.push({ x, *prevCol + 1 });
vis[x][*prevCol + 1] = cnt;
}
if (*prevRow != -1 && vis[*prevRow + 1][y] != cnt) { // left
q.push({ *prevRow + 1, y });
vis[*prevRow + 1][y] = cnt;
}
if (*nextRow != mRow && vis[*nextRow - 1][y] != cnt) { //right
q.push({ *nextRow - 1, y });
vis[*nextRow - 1][y] = cnt;
}
q.pop();
}
damage++;
}
return -1;
}