Memory Control
Problem Description
Memory units are numbered from 1 up to N.
A sequence of memory units is called a memory block.
The memory control system we consider now has four kinds of operations:
1. Reset Reset all memory units free.
2. New x Allocate a memory block consisted of x continuous free memory units with the least start number
3. Free x Release the memory block which includes unit x
4. Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)
Where 1<=x<=N.You are request to find out the output for M operations.
Input
Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.
Output
For each “Reset” operation, output “Reset Now”.
For each “New” operation, if it’s possible to allocate a memory block,
output “New at A”,where Ais the least start number,otherwise output “Reject New”.
For each “Free” operation, if it’s possible to find a memory block occupy unit x,
output “Free from A to B”,where A and B refer to the start and end number of the memory block,otherwise output “Reject Free”.
For each “Get” operation, if it’s possible to find the xth memory blocks,
output “Get at A”,where A is its start number,otherwise output “Reject Get”.
Output one blank line after each test case.
Sample Input
6 10
New 2
New 5
New 2
New 2
Free 3
Get 1
Get 2
Get 3
Free 3
Reset
Sample Output
New at 1
Reject New
New at 3
New at 5
Free from 3 to 4
Get at 1
Get at 5
Reject Get
Reject Free
Reset Now
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#define maxn 51000
using namespace std;
inline int L(int th)
{
return (th << 1);
}
inline int R(int th)
{
return ((th << 1) | 1);
}
struct Tree
{
int l, r;
int cover, rely;
int lm, rm, maxl;
int getLen()
{
return r - l;
}
int mid()
{
return ((l + r) >> 1);
}
}stree[maxn * 4];
void build(int l, int r, int th)
{
//printf("%d %d\n", l, r);
stree[th].l = l, stree[th].r = r;
stree[th].cover = stree[th].rely = 0;
stree[th].lm = stree[th].rm = stree[th].maxl = stree[th].getLen();
if (l + 1 == r)
{
return;
}
int m = stree[th].mid();
if (r <= m)
{
build(l, r, L(th));
}
else if (l >= m)
{
build(l, r, R(th));
}
else
{
build(l, m, L(th)), build(m, r, R(th));
}
}
void update(int th, int kind)//rely操作更新
{
stree[th].rely = 1;
stree[th].cover = kind;
if (stree[th].cover == 0)
{
stree[th].lm = stree[th].rm = stree[th].maxl = stree[th].getLen();
}
else
{
stree[th].lm = stree[th].rm = stree[th].maxl = 0;
}
}
void insert(int l, int r, int th, int kind)
{
//printf("insert %d, %d\n", l, r);
if (stree[th].l == l && stree[th].r == r)
{
update(th, kind);
return;
}
if (stree[th].rely)
{
stree[th].rely = 0;
update(L(th), stree[th].cover);
update(R(th), stree[th].cover);
}
stree[th].cover = -1;//设置无效区域，在这里体现不上用处，不更新也行,出于习惯跟逻辑需要
int m = stree[th].mid();
if (r <= m)
{
insert(l, r, L(th), kind);
}
else if (l >= m)
{
insert(l, r, R(th), kind);
}
else
{
insert(l, m, L(th), kind);
insert(m, r, R(th), kind);
}
stree[th].lm = stree[L(th)].lm, stree[th].rm = stree[R(th)].rm;
if (stree[L(th)].lm == stree[L(th)].getLen())
{
stree[th].lm += stree[R(th)].lm;
}
if (stree[R(th)].rm == stree[R(th)].getLen())
{
stree[th].rm += stree[L(th)].rm;
}
stree[th].maxl = max(stree[L(th)].maxl, stree[R(th)].maxl);
stree[th].maxl = max(stree[th].maxl, stree[L(th)].rm + stree[R(th)].lm);
}
int query(int th, int len)
{
if (stree[th].l + 1 == stree[th].r)
{
if (stree[th].maxl >= len)
{
return stree[th].l;
}
return 0;
}
if (stree[th].rely)
{
stree[th].rely = 0;
update(L(th), stree[th].cover);
update(R(th), stree[th].cover);
}
if (stree[th].maxl < len)//该线段最大空白段maxl小于len
{
return 0;
}
if (stree[L(th)].maxl >= len)//左孩子最大空白段满足len
{
return query(L(th), len);
}
else if(stree[L(th)].rm + stree[R(th)].lm >= len)//由两孩子的中间合并满足
{
return stree[L(th)].r - stree[L(th)].rm;
}
else//右孩子满足
{
return query(R(th), len);
}
}
struct Seg
{
int left, right;
};
vector<Seg>list;
int bsc(int key)
{
//查找key所在的位置的后一位，
//如果不存在包含key的线段时：
//1.key比第一个线段小，返回的是0,0-1就等于-1
//2.key比起点最大线段还大，则返回这个线段的后一位，key可能被这个线段包含，可能不被这个线段包含，取决于这个线段的右端点
int l = 0, r = list.size() - 1, m;
while (l <= r)
{
m = (l + r) >> 1;
if (list[m].left > key)
{
r = m - 1;
}
else if (list[m].left <= key)//保证l在满足线段的后一位
{
l = m + 1;
}
}
return l;
}
void show()
{
int i;
for (i = 0; i < list.size(); i++)
{
printf("%d:%d %d\n", i, list[i].left, list[i].right);
}printf("----\n");
}
int main()
{
int len, x, k, n, m, id;
Seg tmp;
while (scanf("%d%d", &n, &m) - EOF)
{
build(1, n + 1, 1);
char op[10];
list.clear();
while (m--)
{
scanf("%s", op);
if (*op == 'N')
{
scanf("%d", &len);
k = query(1, len);
if (k)
{
printf("New at %d\n", k);
insert(k, k + len, 1, 1);
tmp.left = k, tmp.right = k + len;
if (list.size() == 0)
{
list.push_back(tmp);
}
else
{
id = bsc(k);
list.insert(list.begin() + id, tmp);
}
//show();
}
else
{
printf("Reject New\n");
}
}
else if (*op == 'F')
{
scanf("%d", &x);
k = bsc(x) - 1;
if (k == -1 || list[k].right <= x)
{
printf("Reject Free\n");
}
else
{
printf("Free from %d to %d\n", list[k].left, list[k].right - 1);
insert(list[k].left, list[k].right, 1, 0);
list.erase(list.begin() + k, list.begin() + k + 1);
}
}
else if (*op == 'G')
{
scanf("%d", &x);
if (x <= list.size())
{
printf("Get at %d\n", list[x-1].left);
}
else
{
printf("Reject Get\n");
}
}
else if (*op == 'R')
{
insert(1, n + 1, 1, 0);
list.clear();
printf("Reset Now\n");
}
}
printf("\n");
}
return 0;
}
/*
3 100
N 1
N 1
N 1
F 1
N 1
F 2
N 1
F 3
N 2
*/