Submission #343824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343824	2021-01-04T14:16:40 Z	ogibogi2004	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	751 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[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";
		}
		/*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	98 ms	150636 KB	Output is correct
2	Correct	87 ms	150636 KB	Output is correct
3	Correct	87 ms	150764 KB	Output is correct
4	Correct	118 ms	150636 KB	Output is correct
5	Correct	123 ms	150636 KB	Output is correct
6	Correct	125 ms	150764 KB	Output is correct
7	Correct	123 ms	150636 KB	Output is correct
8	Correct	328 ms	150868 KB	Output is correct
9	Correct	575 ms	151148 KB	Output is correct
10	Correct	590 ms	151276 KB	Output is correct
11	Correct	596 ms	151148 KB	Output is correct
12	Correct	594 ms	152812 KB	Output is correct
13	Correct	550 ms	153196 KB	Output is correct
14	Correct	553 ms	153324 KB	Output is correct
15	Runtime error	751 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-