제출 #343823

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

apple

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int MAXM=1e9;
int d,x,y;
struct Node
{
	int l,r;
	int L,R;
	int cnt;
	bool lazy;
	Node(int _l,int _r)
	{
		l=-1;r=-1;
		L=_l;R=_r;
		cnt=0;lazy=0;
	}
	Node()
	{
		l=-1;r=-1;L=-1;R=-1;cnt=0;lazy=0;
	}
};
Node tree[32*MAXN];
int sz=1;
Node merge(int t1,int t2)
{
	Node n1=tree[t1];
	Node n2=tree[t2];
	Node ret(n1.L,n2.R);
	ret.cnt=n1.cnt+n2.cnt;
	ret.l=t1;
	ret.r=t2;
	return ret;
}
void push(int node)
{
	if(tree[node].lazy==0)return;
	tree[node].cnt=tree[node].R-tree[node].L+1;
	if(tree[node].L==tree[node].R)
	{
		tree[node].lazy=0;
		return;
	}
	int mid=(tree[node].L+tree[node].R)/2;
	if(tree[node].l==-1)
	{
		tree[node].l=++sz;
		tree[tree[node].l].L=tree[node].L;
		tree[tree[node].l].R=mid;
	}
	tree[tree[node].l].lazy=1;
	if(tree[node].r==-1)
	{
		tree[node].r=++sz;
		tree[tree[node].r].L=mid+1;
		tree[tree[node].r].R=tree[node].R;
	}
	tree[tree[node].r].lazy=1;
	tree[node].lazy=0;
}
void update(int node,int ql,int qr)
{
	//cout<<node<<" "<<tree[node].L<<" "<<tree[node].R<<" "<<ql<<" "<<qr<<endl;
	push(node);
	if(tree[node].L>qr||tree[node].R<ql)return;
	if(tree[node].L>=ql&&tree[node].R<=qr)
	{
		tree[node].lazy=1;
		push(node);
		return;
	}
	int mid=(tree[node].L+tree[node].R)/2;
	if(tree[node].l==-1)
	{
		tree[node].l=++sz;
		tree[tree[node].l].L=tree[node].L;
		tree[tree[node].l].R=mid;
	}
	if(tree[node].r==-1)
	{
		tree[node].r=++sz;
		tree[tree[node].r].L=mid+1;
		tree[tree[node].r].R=tree[node].R;
	}
	update(tree[node].l,ql,qr);
	update(tree[node].r,ql,qr);
	tree[node]=merge(tree[node].l,tree[node].r);
}
int query(int node,int ql,int qr)
{
	push(node);
	if(tree[node].R<ql||tree[node].L>qr)return 0;
	//cout<<tree[node].L<<" "<<tree[node].R<<" "<<tree[node].cnt<<endl;
	if(tree[node].R<=qr&&tree[node].L>=ql)return tree[node].cnt;
	int mid=(tree[node].L+tree[node].R)/2;
	if(tree[node].l==-1)
	{
		tree[node].l=++sz;
		tree[tree[node].l].L=tree[node].L;
		tree[tree[node].l].R=mid;
	}
	if(tree[node].r==-1)
	{
		tree[node].r=++sz;
		tree[tree[node].r].L=mid+1;
		tree[tree[node].r].R=tree[node].R;
	}
	return query(tree[node].l,ql,qr)+query(tree[node].r,ql,qr);
}
int main()
{
	tree[1].cnt=0;
	tree[1].l=-1;
	tree[1].r=-1;
	tree[1].L=1;
	tree[1].R=MAXM;
	int m,c=0;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		//cout<<"??\n";
		cin>>d>>x>>y;
		//cout<<"*\n";
		x+=c;y+=c;
		//cout<<"**\n";
		if(d==1)
		{
			c=query(1,x,y);
			cout<<c<<endl;
		}
		else
		{
			//cout<<"?\n";
			update(1,x,y);
			//cout<<"??\n";
		}
		/*for(auto xd:tree)
		{
			if(xd.L==-1)continue;
			cout<<xd.L<<" "<<xd.R<<" "<<xd.cnt<<endl;
		}*/
	}
return 0;
}

• Subtask 1: 0 / 100