Memory Control

Title 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 description

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 description

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

The main idea of the topic

Multi group input
First enter a number n Represents the memory length , Next, enter a m, On behalf of m Operations .
There are four operations
The first is Reset operation , Will empty all memory . That is, release all memory
Second operation New operation , Get a length of x Of memory , And output the address of the first memory . If not, the output rejects creation
Third operation Free operation , Release x The memory segment in which it is located , Be careful x Not necessarily the first address . If the release is not needed at present, the output rejects the release
The fourth operation ,Get operation , Output No x The first address of a memory segment , If there is no x Segment memory , The output refuses to get .

Topic analysis

This is obviously a segment tree of interval modified merging interval problem . such Reset and New The operation is easy to write , however Free There are some problems with the operation . We can create one vector, If New A new area , So let's insert it in the right place , Guarantee vector Overall order . OK, we can use two points to check Free Your first address . meanwhile Get Operation direct access vector The elements are .

AC Code

//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
    
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    
	return a * b / gcd(a, b);
}
inline ll read() {
    
	ll c = getchar(), Nig = 1, x = 0;
	while (!isdigit(c) && c != '-')c = getchar();
	if (c == '-')Nig = -1, c = getchar();
	while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
	return Nig * x;
}
inline void out(ll a) {
    
	if (a < 0)putchar('-'), a = -a;
	if (a > 9)out(a / 10);
	putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
    
	ll res = 1;
	while (n > 0) {
    
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}
#define read read()
const int N = 50000;
struct node {
    
	ll sum, rmaxn, lmaxn;
	int lazy;
}tree[N * 4 + 7];
void creat(int l, int r, int rt)
{
    
	int len = r - l + 1;
	int mid = l + r >> 1;
	tree[rt] = node{
     len,len,len,0 };
	if (l == r)return;
	creat(l, mid, rt << 1);
	creat(mid + 1, r, rt << 1 | 1);
}

void push_up(int l, int r, int rt)
{
    
	int mid = l + r >> 1;
	if (tree[rt << 1].sum == mid - l + 1)
		tree[rt].lmaxn = tree[rt << 1].sum + tree[rt << 1 | 1].lmaxn;
	else
		tree[rt].lmaxn = tree[rt << 1].lmaxn;
	if (tree[rt << 1 | 1].sum == r - mid)
		tree[rt].rmaxn = tree[rt << 1 | 1].sum + tree[rt << 1].rmaxn;
	else
		tree[rt].rmaxn = tree[rt << 1 | 1].rmaxn;
	tree[rt].sum = tree[rt << 1].rmaxn + tree[rt << 1 | 1].lmaxn;
	tree[rt].sum = max(tree[rt << 1 | 1].sum, max(tree[rt << 1].sum, tree[rt].sum));
}
void push_down(int l, int r, int rt)
{
    
	int mid = l + r >> 1;
	if (tree[rt].lazy)
	{
    
		if (tree[rt].lazy == 1)
		{
    
			tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 1;
			tree[rt << 1].lmaxn = tree[rt << 1].rmaxn = tree[rt << 1].sum = 0;
			tree[rt << 1 | 1].lmaxn = tree[rt << 1 | 1].rmaxn = tree[rt << 1 | 1].sum = 0;
		}
		else
		{
    
			tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 2;
			tree[rt << 1].lmaxn = tree[rt << 1].rmaxn = tree[rt << 1].sum = mid - l + 1;
			tree[rt << 1 | 1].lmaxn = tree[rt << 1 | 1].rmaxn = tree[rt << 1 | 1].sum = r - mid;
		}
		tree[rt].lazy = 0;
	}
}
void update(int L, int R, int mark, int l, int r, int rt)
{
    
	if (L <= l && r <= R)
	{
    
		if (mark == 1)
			tree[rt].sum = tree[rt].lmaxn = tree[rt].rmaxn = 0;
		else
			tree[rt].sum = tree[rt].lmaxn = tree[rt].rmaxn = r - l + 1;
		tree[rt].lazy = mark;
		return;
	}
	if (tree[rt].lazy)push_down(l, r, rt);
	int mid = l + r >> 1;
	if (L <= mid)update(L, R, mark, l, mid, rt << 1);
	if (R > mid)update(L, R, mark, mid + 1, r, rt << 1 | 1);
	push_up(l, r, rt);
}
ll query(int len, int l, int r, int rt)
{
    
	if (l == r)return l;
	if (tree[rt].lazy)push_down(l, r, rt);
	int mid = l + r >> 1;
	if (tree[rt << 1].sum >= len)return query(len, l, mid, rt << 1);
	if (tree[rt << 1].rmaxn + tree[rt << 1 | 1].lmaxn >= len)return mid - tree[rt << 1].rmaxn + 1;
	return query(len, mid + 1, r, rt << 1 | 1);
}
struct Node {
    
	ll sta, end;
};
vector<Node>rem;
bool judge(int mid, int num)
{
    
	return rem[mid].sta <= num;
}
int find(int num)
{
    
	int id = -1;
	int l = 0, r = rem.size() - 1;
	while (l <= r)
	{
    
		int mid = l + r >> 1;
		if (judge(mid, num))
		{
    
			id = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return id;
}
void solve(int n, int m)
{
    
	rem.clear();
	memset(tree, 0, sizeof(tree));
	creat(1, n, 1);
	while (m--)
	{
    
		char mark[10];
		scanf("%s", mark);
		if (mark[0] == 'N')
		{
    
			int num = read;
			if (tree[1].sum < num)
				puts("Reject New");
			else
			{
    
				ll sta = query(num, 1, n, 1);
				update(sta, sta + num - 1, 1, 1, n, 1);
				printf("New at %d\n", sta);
				int id = find(sta) + 1;
				rem.insert(rem.begin() + id, Node{
     sta,sta + num - 1 });
			}
		}
		else if (mark[0] == 'R')
		{
    
			update(1, n, 2, 1, n, 1);
			rem.clear();
			puts("Reset Now");
		}
		else if (mark[0] == 'F')
		{
    
			int num = read;
			int id = find(num);
			if (id == -1 || !(rem[id].sta <= num && rem[id].end >= num))
				puts("Reject Free");
			else
			{
    
				printf("Free from %d to %d\n", rem[id].sta, rem[id].end);
				update(rem[id].sta, rem[id].end, 2, 1, n, 1);
				rem.erase(rem.begin() + id);
			}
		}
		else
		{
    
			int num = read;
			if (num > rem.size())
				puts("Reject Get");
			else
				printf("Get at %d\n", rem[num - 1].sta);
		}
	}
}
int main()
{
    
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF)
	{
    
		solve(n, m);
		puts("");
	}
}

By-Round Moon