Submission #343832

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343832	2021-01-04T14:20:03 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	761 ms	219140 KB

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[92*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";
		}
		if(sz>90*MAXN)
		{
			return 0;
		}
		/*for(auto xd:tree)
		{
			if(xd.L==-1)continue;
			cout<<xd.L<<" "<<xd.R<<" "<<xd.cnt<<endl;
		}*/
	}
return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	216428 KB	Output is correct
2	Correct	122 ms	216428 KB	Output is correct
3	Correct	121 ms	216428 KB	Output is correct
4	Correct	150 ms	216428 KB	Output is correct
5	Correct	162 ms	216556 KB	Output is correct
6	Correct	188 ms	216428 KB	Output is correct
7	Correct	157 ms	216428 KB	Output is correct
8	Correct	362 ms	216556 KB	Output is correct
9	Correct	608 ms	216812 KB	Output is correct
10	Correct	618 ms	216812 KB	Output is correct
11	Correct	639 ms	217032 KB	Output is correct
12	Correct	653 ms	217092 KB	Output is correct
13	Correct	592 ms	217068 KB	Output is correct
14	Correct	600 ms	216940 KB	Output is correct
15	Correct	740 ms	217344 KB	Output is correct
16	Correct	731 ms	219052 KB	Output is correct
17	Correct	633 ms	219140 KB	Output is correct
18	Correct	615 ms	219120 KB	Output is correct
19	Correct	754 ms	219116 KB	Output is correct
20	Correct	761 ms	219028 KB	Output is correct