Memory Control

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4418 Accepted Submission(s): 1056

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

Source 2009 Multi-University Training Contest 7 - Host by FZU

题意：

Reset:清空内存

New x:申请长度为x的内存

Free x:释放x所在的内存块

Get x:询问x所在内存块的起点

分析：

New操作用线段树，找到能容纳x的最左的位置，维护节点的左/右起最长连续0的长度和对应区间内最长连续0的长度。

把现有内存块保存，用二分查找/更新即可，注意Reset时要清空。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
                #include
                
                  #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm #define maxn 200007 using namespace std; int setv[maxn<<2]; int lsum0[maxn<<2],rsum0[maxn<<2],msum0[maxn<<2]; struct Memory { int l,r; }; vector
                 
                   v; inline void pushup(int k,int l,int r) { int lc=k*2+1,rc=k*2+2,m=l+r>>1; if (lsum0[lc]==m-l) lsum0[k]=lsum0[lc]+lsum0[rc]; else lsum0[k]=lsum0[lc]; if (rsum0[rc]==r-m) rsum0[k]=rsum0[rc]+rsum0[lc]; else rsum0[k]=rsum0[rc]; msum0[k]=max(rsum0[lc]+lsum0[rc],max(msum0[lc],msum0[rc])); } inline void pushdown(int k,int l,int r) { if (setv[k]!=-1) { int lc=k*2+1,rc=k*2+2,m=l+r>>1; setv[lc]=setv[rc]=setv[k]; lsum0[lc]=rsum0[lc]=msum0[lc]=setv[k]?0:m-l; lsum0[rc]=rsum0[rc]=msum0[rc]=setv[k]?0:r-m; setv[k]=-1; } } void update(int a,int b,int v,int k,int l,int r) { if (b<=l || r<=a) return ; if (a<=l && r<=b) { setv[k]=v; lsum0[k]=rsum0[k]=msum0[k]=v?0:r-l; } else { pushdown(k,l,r); update(a,b,v,k*2+1,l,l+r>>1); update(a,b,v,k*2+2,l+r>>1,r); pushup(k,l,r); } } int query(int w,int k,int l,int r) { int lc=k*2+1,rc=k*2+2,m=l+r>>1; if (r-l==1) return l; if (r-l!=1) pushdown(k,l,r); if (msum0[lc]>=w) return query(w,lc,l,m); if (rsum0[lc]+lsum0[rc]>=w) return m-rsum0[lc]; return query(w,rc,m,r); } int bin_search(int k) { int l=0,r=v.size()-1,ans=-1; while (l<=r) { itn mid=l+r>>1; if (v[mid].l<=k) { l=mid+1; ans=mid; } else { r=mid-1; } } return ans; } int main() { #ifndef ONLINE_JUDGE freopen(/home/fcbruce/文档/code/t,r,stdin); #endif // ONLINE_JUDGE int n,m,w,a,b,p; char op[10]; while (~scanf(%d %d,&n,&m)) { v.clear(); update(0,n,0,0,0,n); while (m--) { scanf(%s,op); if (op[0]=='R') { v.clear(); puts(Reset Now); update(0,n,0,0,0,n); continue; } if (op[0]=='N') { scanf(%d,&w); if (w<=msum0[0]) { a=query(w,0,0,n); b=a+w; update(a,b,1,0,0,n); printf(New at %d ,a+1); Memory temp; temp.l=a+1; temp.r=b; int id=bin_search(a+1)+1; v.insert(v.begin()+id,temp); } else puts(Reject New); continue; } if (op[0]=='F') { scanf(%d,&p); int id=bin_search(p); if (id==-1 || v[id].r
                  
                   ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BestCoder Round #1	下一篇：易学设计模式看书笔记(3) - 工厂..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: