P2894 [USACO08FEB]Hotel G

#include<bits/stdc++.h>
using namespace std;
class segment_tree{
	public:
		int n,m;
		struct tree{
			int len;
			int lm,rm;
			int mm;
			int lazy_tag;
			#define ls (k<<1)
			#define rs (k<<1|1)
			#define len(k) t[k].len
			#define lm(k) t[k].lm
			#define rm(k) t[k].rm
			#define mm(k) t[k].mm
			#define tag(k) t[k].lazy_tag
		}t[500001];
		#define mid (l+r>>1)
		void build(int k,int l,int r){
			len(k)=lm(k)=rm(k)=mm(k)=r-l+1;
			if(l==r)return;
			build(ls,l,mid);
			build(rs,mid+1,r);
			return;
		}
		void pushdown(int k)
		{
			if(tag(k)==0)return;
			tag(ls)=tag(rs)=tag(k);
			mm(ls)=lm(ls)=rm(ls)=(tag(k)==1?len(ls):0);
			mm(rs)=lm(rs)=rm(rs)=(tag(k)==1?len(rs):0);
			tag(k)=0;
		}
		void get_size(int k)
		{
			lm(k)=(mm(ls)==len(ls)?mm(ls)+lm(rs):lm(ls));
			rm(k)=(mm(rs)==len(rs)?mm(rs)+rm(ls):rm(rs));
			mm(k)=max(max(mm(ls),mm(rs)),rm(ls)+lm(rs));
			return;
		}
		void update(int k,int l,int r,int x,int y,int Tag)
		{
			if(l>=x&&r<=y)
			{
				mm(k)=lm(k)=rm(k)=(Tag==1?len(k):0);
				tag(k)=Tag;
				return;
			}
			pushdown(k);
			if(x<=mid)update(ls,l,mid,x,y,Tag);
			if(y>mid)update(rs,mid+1,r,x,y,Tag);
			get_size(k);
		}
		int query(int k,int l,int r,int Size)
		{
			if(l==r)return l;
			pushdown(k); 
			if(mm(ls)>=Size)return query(ls,l,mid,Size);
			if(rm(ls)+lm(rs)>=Size)return mid-rm(ls)+1;
			return query(rs,mid+1,r,Size);
		}
};
int main()
{
	segment_tree st;
	cin>>st.n>>st.m;
	st.build(1,1,st.n);
	while(st.m--)
	{
		char op;int x,y;
		cin>>op>>x;
		if(op=='1'){
			if(st.mm(1)<x){
				cout<<"0"<<endl;
				continue;
			}
			y=st.query(1,1,st.n,x);
			cout<<y<<endl;
			st.update(1,1,st.n,y,y+x-1,2);
		}else{
			cin>>y;
			st.update(1,1,st.n,x,y+x-1,1);
		}
	}
}