Submission #343829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343829	2021-01-04T14:18:17 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	982 ms	262144 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[80*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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	188140 KB	Output is correct
2	Correct	108 ms	188140 KB	Output is correct
3	Correct	108 ms	188268 KB	Output is correct
4	Correct	134 ms	188300 KB	Output is correct
5	Correct	150 ms	188364 KB	Output is correct
6	Correct	145 ms	188396 KB	Output is correct
7	Correct	144 ms	188356 KB	Output is correct
8	Correct	353 ms	188472 KB	Output is correct
9	Correct	600 ms	188524 KB	Output is correct
10	Correct	610 ms	188652 KB	Output is correct
11	Correct	618 ms	188652 KB	Output is correct
12	Correct	608 ms	188652 KB	Output is correct
13	Correct	577 ms	188708 KB	Output is correct
14	Correct	584 ms	188780 KB	Output is correct
15	Runtime error	982 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-