Submission #343536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343536	2021-01-04T08:12:47 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	843 ms	262148 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int cnt_nodes=0;
struct tree
{
	struct node
	{
		node *l,*r;
		int minval,cnt;
		int L,R;
		int lazy;
		node(int _l,int _r)
		{
			l=nullptr;
			r=nullptr;
			minval=0;cnt=_r-_l+1;
			L=_l;R=_r;
		}
	};
	node* root=nullptr;
	node* xd;
	node* merge(node *n1,node *n2)
	{
		if(!n1)return n2;
		if(!n2)return n1;
		node *ret=new node(n1->L,n2->R);
		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)
	{
		if(!t)t=new node(L,R);
		if(t->lazy>=1)
		{
			if(t->L!=t->R)
			{
				int mid=(t->L+t->R)/2;
				if(t->l)
				{
					t->l->lazy+=t->lazy;
				}
				else 
				{
					t->l=new node(L,mid);
					t->l->lazy+=t->lazy;
				}
				if(t->r)
				{
					t->r->lazy+=t->lazy;
				}
				else 
				{
					t->r=new node(mid+1,R);
					t->r->lazy+=t->lazy;
				}
			}
			t->minval+=t->lazy;
			t->lazy=0;
		}
		return t;
	}
	node* upd(node *t,int L,int R,int ql,int qr)
	{
		t=push(t,L,R);
		if(L>qr||R<ql)return t;
		if(L>=ql&&R<=qr)
		{
			t->lazy=1;
			t=push(t,L,R);
			return t;
		}
		int mid=(L+R)/2;
		t->l=upd(t->l,L,mid,ql,qr);
		t->r=upd(t->r,mid+1,R,ql,qr);
		t=merge(t->l,t->r);
		return t;
	}
	node* query(node *t,int L,int R,int ql,int qr)
	{	
		t=push(t,L,R);
		if(L>qr||R<ql)return NULL;
		if(L>=ql&&R<=qr)
		{
			return t;
		}
		int mid=(L+R)/2;
		return merge(query(t->l,L,mid,ql,qr),query(t->r,mid+1,R,ql,qr));
	}
	void print(node* t)
	{
		if(!t)return;
		cnt_nodes++;
		cout<<t->L<<" "<<t->R<<" "<<t->minval<<" "<<t->cnt<<endl;
		print(t->l);
		print(t->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;
	while(m--)
	{
		cin>>d>>x>>y;
		x+=c;y+=c;
		if(d==1)
		{
			st.xd=st.query(st.root,0,INF,x,y);
			if(st.xd->minval>0)
			{
				c=y-x+1;
			}
			else c=y-x+1-st.xd->cnt;
			cout<<c<<endl;
		}
		else st.root=st.upd(st.root,0,INF,x,y);
		/*st.print(st.root);
		cout<<"fdsf "<<cnt_nodes<<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	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	53 ms	21484 KB	Output is correct
5	Correct	63 ms	25964 KB	Output is correct
6	Correct	63 ms	26092 KB	Output is correct
7	Correct	64 ms	25964 KB	Output is correct
8	Correct	469 ms	155244 KB	Output is correct
9	Runtime error	843 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Halted	0 ms	0 KB	-