제출 #343658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343658		ogibogi2004	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	940 ms	262148 KiB

apple

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct tree
{
	struct node
	{
		node *l,*r;
		bool minval;
		int cnt;
		bool lazy;
		node(int _cnt)
		{
			l=nullptr;
			r=nullptr;
			minval=0;cnt=_cnt;
		}
	};
	node* root=nullptr;
	node* xd;
	node* merge(node *n1,node *n2,int L,int R)
	{
		node *ret=new node(R-L+1);
		int mid=(L+R)/2;
		if(!n1)
		{
			tie(ret->minval,ret->cnt)=make_pair(n2->minval,n2->cnt);
			if(ret->minval==0)ret->cnt+=mid-L+1;
			else 
			{
				ret->minval=0;
				ret->cnt=mid-L+1;
			}
			ret->r=n2;
			return ret;
		}
		if(!n2)
		{
			tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt);
			if(ret->minval==0)ret->cnt+=R-mid;
			else 
			{
				ret->minval=0;
				ret->cnt=R-mid;
			}
			ret->l=n1;
			return ret;
		}
		if(n1->minval==n2->minval)
		{
			tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt+n2->cnt);
		}
		else tie(ret->minval,ret->cnt)=min(make_pair(n1->minval,n1->cnt),make_pair(n2->minval,n2->cnt));
		ret->l=n1;ret->r=n2;
		return ret;
	}
	node* push(node *t,int L,int R)
	{
		//cout<<L<<" "<<R<<" pushed\n";
		if(!t)t=new node(R-L+1);
		if(t->lazy)
		{
			if(L!=R)
			{
				int mid=(L+R)/2;
				if(t->l)
				{
					t->l->lazy=1;
				}
				else 
				{
					t->l=new node(mid-L+1);
					t->l->lazy=1;
				}
				if(t->r)
				{
	 				t->r->lazy=1;
				}
				else 
				{
					t->r=new node(R-mid);
					t->r->lazy=1;
				}
			}
			t->minval=1;
			t->lazy=0;
		}
		return t;
	}
	node* upd(node *t,int L,int R,int ql,int qr)
	{
		//cout<<L<<" "<<R<<"\n";
		//op++;
		//if(op>100)return;
		//cout<<"?\n";
		//bool pr=0;
		//if(t&&t->lazy)pr=1;
		t=push(t,L,R);
		/*if(pr)
		{
			cout<<"shre\n";
			if(t->l)cout<<t->l->minval<<" "<<t->l->lazy<<endl;
			if(t->r)cout<<t->r->minval<<" "<<t->r->lazy<<endl;
		}*/
		//cout<<"?\n";
		if(L>qr||R<ql)return NULL;
		if(L>=ql&&R<=qr)
		{
			t->lazy=1;
			t=push(t,L,R);
			//if(t)cout<<L<<" "<<R<<endl;
			return t;
		}
		int mid=(L+R)/2;
		if(mid+1>qr)
		{
			//cout<<"1:\n";
			//if(!t->l)cout<<"wtf\n";
			//else cout<<t->l->minval<<" "<<t->l->cnt<<endl;
			//if(!t->l)t->l=new node(mid-L+1);
			//cout<<"$#@$#@\n";
			t->l=upd(t->l,L,mid,ql,qr);
			//cout<<":1\n";
		}
		else if(mid<ql)
		{
			//cout<<"2:\n";
			t->r=upd(t->r,mid+1,R,ql,qr);
			//cout<<":2\n";
		}
		else
		{
			//cout<<"3:\n";
			t->l=upd(t->l,L,mid,ql,qr);
			t->r=upd(t->r,mid+1,R,ql,qr);
			//cout<<":3\n";
		}
		if(t->l&&t->l->lazy)t->l=push(t->l,L,mid);
		if(t->r&&t->r->lazy)t->r=push(t->r,mid+1,R);
		//cout<<L<<" "<<R<<endl;
		//cout<<"t->l:";
		//if(t->l)cout<<t->l->minval<<" "<<t->l->cnt<<" "<<t->l->lazy<<endl;
		//else cout<<endl;
		//cout<<"t->r:";
		//if(t->r)cout<<t->r->minval<<" "<<t->r->cnt<<" "<<t->r->lazy<<endl;
		//else cout<<endl;
		t=merge(t->l,t->r,L,R);
		//cout<<"merged to:\n";
		//cout<<t->minval<<" "<<t->cnt<<" "<<t->lazy<<endl;
		return t;
		//if(t)cout<<L<<" "<<R<<endl;
	}
	int query(node *t,int L,int R,int ql,int qr)
	{
		//cout<<L<<" "<<R<<endl;
		t=push(t,L,R);
		if(L>qr||R<ql)return 0;
		if(L>=ql&&R<=qr)
		{
			if(t->minval==0)return t->cnt;
			else return 0;
			//return t;
		}
		int mid=(L+R)/2;
		if(mid<ql)return query(t->r,mid+1,R,ql,qr);
		else if(mid+1>qr)return query(t->l,L,mid,ql,qr);
		return query(t->l,L,mid,ql,qr)+query(t->r,mid+1,R,ql,qr);
	}
	void print(node* t,int L,int R)
	{
		if(!t)return;
		//if(t->l&&t->r)t=push(t,L,R);
		//cout<<L<<" "<<R<<" "<<t->minval<<" "<<t->cnt<<" "<<t->lazy<<endl;
		print(t->l,L,(L+R)/2);
		print(t->r,(L+R)/2+1,R);
	}
}st;
int main()
{
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);*/
	int c=0;
	int m,d,x,y,xd;
	cin>>m;
	/*if(m>60000)
	{
		cout<<0<<endl;
		return 0;
	}*/
	while(m--)
	{
		cin>>d>>x>>y;
		x+=c;y+=c;
		//cout<<"#@$%$#@$\n";
		if(d==1)
		{
			xd=st.query(st.root,1,INF,x,y);
			c=y-x+1-xd;
			cout<<c<<endl;
		}
		else
		{
			//cout<<"5%\n";
			st.root=st.upd(st.root,1,INF,x,y);
		}
		//st.print(st.root,1,INF);
		//cout<<"fdsf "<<cnt_nodes<<endl;
		//int xd=st.query(st.root,1,INF,1,INF);
		//cout<<xd<<" "<<INF-xd<<endl;
		//cnt_nodes=0;
	}
	/*for(int i=0;i<10;i++)
	{
		for(int j=i+1;j<10000;j++)
		{
			st.root=st.upd(st.root,0,INF,i,j);
		}
	}
	st.print(st.root);
	cout<<cnt_nodes<<endl;*/
return 0;
}

• Subtask 1: 0 / 100