답안 #343654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343654	2021-01-04T10:37:28 Z	ogibogi2004	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	941 ms	262144 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int cnt_nodes=0,op;
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);
		cnt_nodes++;
		//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;
	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)
		{
			int 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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	51 ms	16364 KB	Output is correct
5	Correct	62 ms	20204 KB	Output is correct
6	Correct	60 ms	20332 KB	Output is correct
7	Correct	65 ms	20332 KB	Output is correct
8	Correct	418 ms	125420 KB	Output is correct
9	Correct	855 ms	234604 KB	Output is correct
10	Correct	918 ms	249708 KB	Output is correct
11	Correct	912 ms	261464 KB	Output is correct
12	Runtime error	941 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Halted	0 ms	0 KB	-