답안 #343694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343694	2021-01-04T11:46:08 Z	ogibogi2004	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	926 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 push(node* &t,int L,int R)
	{
		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;
	}
	void upd(node* &t,int L,int R,int ql,int qr)
	{
		if(L>qr||R<ql)return;
		push(t,L,R);
		if(L>=ql&&R<=qr)
		{
			t->lazy=1;
			return;
		}
		int mid=(L+R)/2;
		if(mid+1>qr)
		{
			upd(t->l,L,mid,ql,qr);
		}
		else if(mid<ql)
		{
			upd(t->r,mid+1,R,ql,qr);
		}
		else
		{
			upd(t->l,L,mid,ql,qr);
			upd(t->r,mid+1,R,ql,qr);
		}
		if(t->l&&t->l->lazy)push(t->l,L,mid);
		if(t->r&&t->r->lazy)push(t->r,mid+1,R);
		t=merge(t->l,t->r,L,R);
		return;
	}
	int query(node *t,int L,int R,int ql,int qr)
	{
		if(L>qr||R<ql)return 0;
		push(t,L,R);
		if(L>=ql&&R<=qr)
		{
			if(t->minval==0)return t->cnt;
			else return 0;
		}
		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;
		print(t->l,L,(L+R)/2);
		print(t->r,(L+R)/2+1,R);
	}
}st;
int main()
{
	int c=0;
	int m,d,x,y,xd;
	cin>>m;
	while(m--)
	{
		cin>>d>>x>>y;
		x+=c;y+=c;
		if(d==1)
		{
			xd=st.query(st.root,1,INF,x,y);
			c=y-x+1-xd;
			cout<<c<<endl;
		}
		else
		{
			st.upd(st.root,1,INF,x,y);
		}
	}
return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	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	50 ms	16236 KB	Output is correct
5	Correct	59 ms	20076 KB	Output is correct
6	Correct	60 ms	19948 KB	Output is correct
7	Correct	62 ms	20204 KB	Output is correct
8	Correct	413 ms	125292 KB	Output is correct
9	Correct	845 ms	232556 KB	Output is correct
10	Correct	887 ms	247924 KB	Output is correct
11	Correct	926 ms	259820 KB	Output is correct
12	Runtime error	913 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Halted	0 ms	0 KB	-