ural1037 Memory Management

Memory Management

Time limit: 2.0 second
Memory limit: 64 MB

Background

Don't you know that at school pupils’ programming contest a new computer language has been developed. We call it D++. Generally speaking it doesn't matter if you know about it or not. But to run programs written in D++ we need a new operating system. It should be rather powerful and complex. It should work fast and have a lot of possibilities. But all this should be done in a future.

And now you are to… No. You should not devise the name for the operating system. You are to write the first module for this new OS. And of course it's the memory management module. Let's discuss how it is expected to work.

Problem

Our operating system is to allocate memory in pieces that we’ll call “blocks”. The blocks are to be numbered by integers from 1 up to N. When operating system needs more memory it makes a request to the memory management module. To process this request the memory management module should find free memory block with the least number. You may assume that there are enough blocks to process all requests.

Now we should define the meaning of words “free block”. At the moment of first request to the memory management module all blocks are considered to be free. Also a block becomes free when there were no requests to it during T minutes.

You may wonder about a notion “request to allocated blocks”. What does it mean, “request to allocated block”? The answer is simple: at any time the memory management module may be requested to access a given block. To process this request the memory management module should check if the requested block is really allocated. If it is, the request is considered to be successful and the block remains allocated for T minutes more. Otherwise the request is failed.

That's all about the algorithms of the memory management block. You are to implement them for N = 30 000 and T = 10 minutes.

Input

Each line of input contains a request for memory block allocation or memory block access. Memory allocation request has a form:

<Time> +

where <Time> is a nonnegative integer number not greater than 65 000. Time is given in seconds. Memory block access request has a form:

<Time> . <BlockNo>

where <Time> meets conditions mentioned above for the memory allocation request and <BlockNo> is an integer value in range from 1 to N. There will be no more than 80000 requests.

Output

For each line of input you should print exactly one line with a result of request processing. For memory allocation request you are to write an only integer — a number of allocated block. As it was mentioned above you may assume that every request can be satisfied, there will be no more than Nsimultaneously allocated blocks. For memory block access request you should print the only character:

'+' if request is successful (i.e. block is really allocated);
'-' if request fails (i.e. block with number given is free, so it can't be accessed).

Requests are arranged by their times in an increasing order. Requests with equal times should be processed as they appear in input.

Sample

input	output
1 + 1 + 1 + 2 . 2 2 . 3 3 . 30000 601 . 1 601 . 2 602 . 3 602 + 602 + 1202 . 2	1 2 3 + + - - + - 1 3 -

分析：树状数组来找当前第一个空闲内存；

　　　优先队列来判断内存是否过期，注意优先队列里的时间不一定是实际到期时间，要注意判断；

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=3e4+10;
const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}
int n,m,k,t,now[maxn],a[maxn];
void add(int x,int y)
{
    for(int i=x;i<=maxn-5;i+=(i&(-i)))
        a[i]+=y;
}
int get(int x)
{
    int res=0;
    for(int i=x;i;i-=(i&(-i)))
        res+=a[i];
    return res;
}
struct node
{
    int t,id;
    node(int _t,int _id)
    {
        t=_t,id=_id;
    }
    bool operator<(const node&p)const
    {
        return t>p.t;
    }
};
char op[2];
priority_queue<node>q;
int main()
{
    int i,j;
    memset(now,-1,sizeof now);
    while(~scanf("%d",&n))
    {
        scanf("%s",op);
        if(op[0]=='.'){
            scanf("%d",&m);
            if(now[m]>=n)
            {
                now[m]=n+599;
                puts("+");
            }
            else puts("-");
        }
        else
        {
            while(!q.empty()&&q.top().t<n){
                    if(now[q.top().id]<n)add(q.top().id,-1);
                    else q.push(node(now[q.top().id],q.top().id));
                    q.pop();
            }
            int l=1,r=30000,ret;
            while(l<=r)
            {
                int mid=l+r>>1;
                if(get(mid)<mid)ret=mid,r=mid-1;
                else l=mid+1;
            }
            add(ret,1);
            now[ret]=n+599;
            q.push(node(now[ret],ret));
            printf("%d
",ret);
        }
    }
    //system("pause");
    return 0;
}