Hotel
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 12446   Accepted: 5363

Description

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation
residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤
Di ≤ N) and approach the front desk to check in. Each group
i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers
r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of
r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and
Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤
Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and
Di (b) Three space-separated integers representing a check-out: 2,
Xi, and Di

Output

* Lines 1.....: For each check-in request, output a single line with a single integer
r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

Sample Input

10 6

1 3

1 3

1 3

1 3

2 5 5

1 6

Sample Output

1

4

7

0

5

代码：

/* ***********************************************

Author :rabbit

Created Time :2014/11/1 12:57:54

File Name :4.cpp

************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <sstream>

#include <stdlib.h>

#include <string.h>

#include <limits.h>

#include <string>

#include <time.h>

#include <math.h>

#include <queue>

#include <stack>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define eps 1e-8

#define pi acos(-1.0)

typedef long long ll;

const int maxn=200200;

struct Node;

Node *null;

struct Node{

	Node *ch[2],*fa;

	int size;

	int lsum,rsum,msum,col,val;

	Node(){

		ch[0]=ch[1]=fa=null;

		col=0;

	}

	inline void setc(Node *p,int d){

		ch[d]=p;

		p->fa=this;

	}

	inline bool d(){

		return fa->ch[1]==this;

	}

	void clear(){

		size=1;

		ch[0]=ch[1]=fa=null;

		lsum=rsum=msum=val=1;

		col=-1;

	}

	inline void push_up(){

		if(this==null)return;

		size=ch[0]->size+ch[1]->size+1;

		lsum=ch[0]->lsum;

		rsum=ch[1]->rsum;

		msum=max(ch[0]->msum,ch[1]->msum);

		if(val){

			msum=max(msum,ch[0]->rsum+ch[1]->lsum+1);

			if(lsum==ch[0]->size)lsum+=ch[1]->lsum+1;

			if(rsum==ch[1]->size)rsum+=ch[0]->rsum+1;

		}

	}

	void update(int c){

		if(this==null)return;

		lsum=rsum=msum=c*size;

		val=col=c;

	}

	inline void push_down(){

		if(this==null)return;

		if(col!=-1){

			ch[0]->update(col);

			ch[1]->update(col);

			col=-1;

		}

	}

};

inline void rotate(Node *x){

	Node *f=x->fa,*ff=x->fa->fa;

	f->push_down();

	x->push_down();

	int c=x->d(),cc=f->d();

	f->setc(x->ch[!c],c);

	x->setc(f,!c);

	if(ff->ch[cc]==f)ff->setc(x,cc);

	else x->fa=ff;

	f->push_up();

}

inline void splay(Node *&root,Node *x,Node *goal){

	while(x->fa!=goal){

		if(x->fa->fa==goal)rotate(x);

		else{

			x->fa->fa->push_down();

			x->fa->push_down();

			x->push_down();

			bool f=x->fa->d();

			x->d()==f?

rotate(x->fa):rotate(x);

			rotate(x);

		}

	}

	x->push_up();

	if(goal==null)root=x;

}

Node *get_kth(Node *r,int k){

	Node *x=r;

	x->push_down();

	while(x->ch[0]->size+1!=k){

		if(k<x->ch[0]->size+1)x=x->ch[0];

		else{

			k-=x->ch[0]->size+1;

			x=x->ch[1];

		}

		x->push_down();

	}

	return x;

}

Node pool[maxn],*tail,*node[maxn],*root;

void build(Node *&x,int l,int r,Node *fa){

	if(l>r)return;

	int mid=(l+r)/2;

	x=tail++;

	x->clear();

	x->fa=fa;

	node[mid]=x;

	build(x->ch[0],l,mid-1,x);

	build(x->ch[1],mid+1,r,x);

	x->push_up();

}

void init(int n){

	tail=pool;

	null=tail++;

	null->fa=null->ch[0]=null->ch[1]=null;

	null->size=0;

	null->val=null->lsum=null->rsum=null->msum=0;null->col=-1;

	Node *p=tail++;

	p->val=p->msum=p->rsum=p->lsum=0;p->col=-1;

	p->size=1;p->ch[0]=p->ch[1]=p->fa=null;

	root=p;

	p=tail++;

	p->val=p->msum=p->rsum=p->lsum=0;p->col=-1;

	p->size=1;p->ch[0]=p->ch[1]=p->fa=null;

	root->setc(p,1);

	build(root->ch[1]->ch[0],1,n,root->ch[1]);

	root->ch[1]->push_up();

	root->push_up();

}

void update(int l,int r,int c){

	splay(root,get_kth(root,l),null);

	splay(root,get_kth(root,r+2),root);

	root->ch[1]->ch[0]->update(c);

	root->ch[1]->push_up();

	root->push_up();

}

int query(int l,int r){

	splay(root,get_kth(root,l),null);

	splay(root,get_kth(root,r+2),root);

	return root->ch[1]->ch[0]->msum;

}

int find(Node *x,int k,int pos){

	x->push_down();

	//cout<<x->msum<<endl;

	if(x->ch[0]->msum>=k)return find(x->ch[0],k,pos);

	pos+=x->ch[0]->size;

	if(x->val&&x->ch[0]->rsum+x->ch[1]->lsum+1>=k)return pos-x->ch[0]->rsum;

	return find(x->ch[1],k,pos+1);

}

int main()

{

     //freopen("data.in","r",stdin);

     //freopen("data.out","w",stdout);

     int n,m;

	 while(~scanf("%d%d",&n,&m)){

		 init(n);

		 //cout<<root->msum<<" "<<root->ch[0]->msum<<" "<<root->ch[1]->msum<<endl;

		 while(m--){

			 int op,x,y;

			 scanf("%d",&op);

			 if(op==1){

				 scanf("%d",&x);

				 if(root->msum<x){

					 puts("0");continue;

				 }

				 int k=find(root,x,0);

				 printf("%d\n",k);

				 update(k,k+x-1,0);

			 }

			 else{

				 scanf("%d%d",&x,&y);

				 update(x,x+y-1,1);

			 }

		 }

	 }

     return 0;

}

/*

int main()

{

	int n,m;

	while(cin>>n>>m) {

		init(n);

		while(m--){

			int op,x,y,z;

			cin>>op;

			if(op==1){

				cin>>x>>y>>z;

				update(x,y,z);

			}

			else{

				cin>>x>>y;

				cout<<query(x,y)<<endl;

			}

		}

	}

	return 0;

}

*/

版权声明：本文博主原创文章。博客，未经同意不得转载。

最新文章

  1. ASP.NET杂谈-一切都从web.config说起（2）（ConfigSections详解-下)
  2. Performance Optimization (2)
  3. ecshop检验邮件是否合法
  4. 使用javah生成.h文件, 出现无法访问android.app,Activity的错误的解决
  5. iOS开发之UIWebView自动滑动到顶部-备
  6. 在CentOS 7下试验Drupal 7
  7. POJ 3340 &amp;amp; HDU 2410 Barbara Bennett&amp;#39;s Wild Numbers（数学）
  8. leetcode第六题--ZigZag Conversion
  9. 编译安装nginx却requires the PCRE library
  10. 搬寝室（经典dp）
  11. C#多线程编程（4）--异常处理+前三篇的总结
  12. 剑指Offer——全排列递归思路
  13. Android中JNI编程详解
  14. 使用POST下载文件
  15. MySQL InnoDB引擎B+树索引简单整理说明
  16. Java static 语句块
  17. js 时间的国际化处理
  18. python标准库介绍——33 thread 模块详解
  19. Eclipse Error: The refactoring does not change any source code
  20. 使用gitblit搭建一个简单的局域网服务器

热门文章

  1. 国内外主流BI厂商对比
  2. InfoQ文章
  3. 基于Visual C++2013拆解世界五百强面试题--题3-打印螺旋数组
  4. JAVA GUI学习 - JTable表格组件学习_A ***
  5. Poj 2371 Questions and answers(排序)
  6. Hibernate_13_QBC查询
  7. UIControl IOS控件编程 及UITextField的讲解
  8. HA for openstack
  9. Objects
  10. linux基本命令－注销、关机、重起