Submission #343661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343661	2021-01-04T10:46:18 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	927 ms	262148 KB

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;
	}
	void/*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;
	}
	/*node*/void 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(L>qr||R<ql)return;
		//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>=ql&&R<=qr)
		{
			t->lazy=1;
			/*t=*/push(t,L,R);
			//if(t)cout<<L<<" "<<R<<endl;
			return;
		}
		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;
		//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.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

#	Verdict	Execution time	Memory	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	49 ms	16236 KB	Output is correct
5	Correct	64 ms	20076 KB	Output is correct
6	Correct	61 ms	19948 KB	Output is correct
7	Correct	59 ms	20204 KB	Output is correct
8	Correct	415 ms	125292 KB	Output is correct
9	Correct	871 ms	232812 KB	Output is correct
10	Correct	883 ms	247916 KB	Output is correct
11	Correct	897 ms	259820 KB	Output is correct
12	Runtime error	927 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Halted	0 ms	0 KB	-