Submission #343830

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343830	2021-01-04T14:19:14 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	591 ms	151444 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[64*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>63*MAXN)
		{
			return 0;
		}
		/*for(auto xd:tree)
		{
			if(xd.L==-1)continue;
			cout<<xd.L<<" "<<xd.R<<" "<<xd.cnt<<endl;
		}*/
	}
return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	150636 KB	Output is correct
2	Correct	86 ms	150636 KB	Output is correct
3	Correct	86 ms	150636 KB	Output is correct
4	Correct	113 ms	150636 KB	Output is correct
5	Correct	125 ms	150636 KB	Output is correct
6	Correct	125 ms	150636 KB	Output is correct
7	Correct	129 ms	150636 KB	Output is correct
8	Correct	335 ms	150892 KB	Output is correct
9	Correct	567 ms	151020 KB	Output is correct
10	Correct	575 ms	151100 KB	Output is correct
11	Correct	591 ms	151148 KB	Output is correct
12	Correct	591 ms	151148 KB	Output is correct
13	Correct	558 ms	151148 KB	Output is correct
14	Correct	557 ms	151080 KB	Output is correct
15	Incorrect	556 ms	151444 KB	Output isn't correct
16	Halted	0 ms	0 KB	-