PKU 3667 Hotel

疲れる問題でした。

解法
「空所の左端の位置」「空所の右端の位置」「空所のサイズ(左端だけもっている)」を遅延更新するsegtreeで持つ。
WAの原因はホテルに人を入れるときの「空所の左端の位置」を人数分右にずらすのを忘れていたからでした。

#include<stdio.h>
#include<algorithm>
using namespace std;
int left[1<<17];
int l_t[1<<17];
int right[1<<17];
int r_t[1<<17];
int sz[1<<17];
int s_t[1<<17];
int find(int a){
	if(sz[1]<a)return -1;
	int L=0;
	int R=65535;
	int ind=1;
	while(L<R){
		if(s_t[ind]){
			s_t[ind]=0;
			s_t[ind*2]=s_t[ind*2+1]=1;
			sz[ind*2]=sz[ind*2+1]=sz[ind];
		}
		if(sz[ind*2]>=a){
			ind=ind*2;
			R=(L+R)/2;
		}else{
			ind=ind*2+1;
			L=(L+R)/2+1;
		}
	}
	return L;
}
void updateS(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		s_t[e]=1;
		sz[e]=f;
		return;
	}
	if(s_t[e]){
		s_t[e]=0;
		s_t[e*2]=s_t[e*2+1]=1;
		sz[e*2]=sz[e*2+1]=sz[e];
	}
	updateS(a,(a+b)/2,c,d,e*2,f);
	updateS((a+b)/2+1,b,c,d,e*2+1,f);
	sz[e]=max(sz[e*2],sz[e*2+1]);
}
void updateL(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		l_t[e]=1;
		left[e]=f;
		return;
	}
	if(l_t[e]){
		l_t[e]=0;
		l_t[e*2]=l_t[e*2+1]=1;
		left[e*2]=left[e*2+1]=left[e];
	}
	updateL(a,(a+b)/2,c,d,e*2,f);
	updateL((a+b)/2+1,b,c,d,e*2+1,f);
	left[e]=min(left[e*2],left[e*2+1]);
}
void updateR(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		r_t[e]=1;
		right[e]=f;
		return;
	}
	if(r_t[e]){
		r_t[e]=0;
		r_t[e*2]=r_t[e*2+1]=1;
		right[e*2]=right[e*2+1]=right[e];
	}
	updateR(a,(a+b)/2,c,d,e*2,f);
	updateR((a+b)/2+1,b,c,d,e*2+1,f);
	right[e]=max(right[e*2],right[e*2+1]);
}
int getL(int a){
	int L=0;
	int R=65535;
	int ind=1;
	while(L<R){
		if(l_t[ind]){
			l_t[ind]=0;
			l_t[ind*2]=l_t[ind*2+1]=1;
			left[ind*2]=left[ind*2+1]=left[ind];
		}
		if((L+R)/2>=a){
			ind=ind*2;
			R=(L+R)/2;
		}else{
			ind=ind*2+1;
			L=(L+R)/2+1;
		}
	}
	return left[a+65536];
}
int getR(int a){
	int L=0;
	int R=65535;
	int ind=1;
	while(L<R){
		if(r_t[ind]){
			r_t[ind]=0;
			r_t[ind*2]=r_t[ind*2+1]=1;
			right[ind*2]=right[ind*2+1]=right[ind];
		}
		if((L+R)/2>=a){
			ind=ind*2;
			R=(L+R)/2;
		}else{
			ind=ind*2+1;
			L=(L+R)/2+1;
		}
	}
	return right[a+65536];
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<(1<<17);i++)left[i]=999999999;
	for(int i=0;i<(1<<17);i++)right[i]=sz[i]=-999999999;
	for(int i=1;i<=a;i++){
		left[65536+i]=1;
		right[65536+i]=a;
	}
	sz[65537]=a;
	for(int i=65535;i>=1;i--){
		left[i]=min(left[i*2],left[i*2+1]);
		right[i]=max(right[i*2],right[i*2+1]);
		sz[i]=max(sz[i*2],sz[i*2+1]);
	}
	for(int i=0;i<b;i++){
		int c;
		scanf("%d",&c);
		if(c==1){
			int d;
			scanf("%d",&d);
			int at=find(d);
			if(at==-1){
				printf("0\n");
			}else{
				int val=sz[65536+at];
				printf("%d\n",at);
				updateL(0,65535,at,getR(at),1,at+d);
				updateL(0,65535,at,at+d-1,1,999999999);
				updateR(0,65535,at,at+d-1,1,-999999999);
				updateS(0,65535,at,at,1,-999999999);
				updateS(0,65535,at+d,at+d,1,val-d);
			}
		}else{
			int d,e;
			scanf("%d%d",&d,&e);
			int l=min(d,getL(d-1));
			int r=max(d+e-1,getR(d+e));
			updateL(0,65535,l,r,1,l);
			updateR(0,65535,l,r,1,r);
			updateS(0,65535,l+1,r,1,0);
			updateS(0,65535,l,l,1,r-l+1);
		}
	}
}

USACO残り9問になりました。