Submission #426794

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426794	2021-06-14T09:51:50 Z	jeqcho	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	632 ms	258392 KB

apple

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int t=0;

struct node
{
	int lx,rx;
	int val=0;
	bool lazy=0;
	node *lefchi=NULL,*rigchi=NULL;
	
	int comb(int a,int b){return a+b;}
	void extend()
	{
		if(!lefchi && rx-lx!=1)
		{
			int md=(lx+rx)/2;
			lefchi=new node({lx,md});
			rigchi=new node({md,rx});
			t+=2;
			assert(t<1e7);
		}
	}
	void refresh()
	{
		if(!lazy)return;
		val=rx-lx;
	}
	void push()
	{
		if(!lazy)return;
		refresh();
		if(rx-lx==1)return;
		extend();
		lefchi->lazy = 1;
		rigchi->lazy = 1;
	}
	
	int query(int lq,int rq)
	{
		if(lq>=rx || rq<=lx)return 0;
		refresh();
		if(lq<=lx && rq>=rx)return val;
		push();
		extend();
		int lef = lefchi->query(lq,rq);
		int rig = rigchi->query(lq,rq);
		return comb(lef,rig);
	}
	void update(int lq,int rq)
	{
		
		if(lq>=rx || rq<=lx)return;
		push();
		if(lq<=lx && rq>=rx)
		{
			lazy=1;
			return;
		}
		extend();
		lefchi->update(lq,rq);
		rigchi->update(lq,rq);
		val = comb(lefchi->query(0,1<<30),rigchi->query(0,1<<30));
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int m;
	cin>>m;
	int c=0;
	node seg({0,1<<30});
	++t;
	while(m--)
	{
		int d,x,y;
		cin>>d>>x>>y;
		if(d==1)
		{
			c=seg.query(c+x,c+y+1);
			cout<<c<<'\n';
		}
		else
		{
			seg.update(c+x,c+y+1);
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	18 ms	5960 KB	Output is correct
5	Correct	21 ms	7116 KB	Output is correct
6	Correct	22 ms	6992 KB	Output is correct
7	Correct	21 ms	7192 KB	Output is correct
8	Correct	181 ms	54140 KB	Output is correct
9	Correct	368 ms	90800 KB	Output is correct
10	Correct	357 ms	103568 KB	Output is correct
11	Correct	367 ms	111624 KB	Output is correct
12	Correct	391 ms	115044 KB	Output is correct
13	Correct	375 ms	134352 KB	Output is correct
14	Correct	349 ms	136000 KB	Output is correct
15	Correct	544 ms	251128 KB	Output is correct
16	Correct	617 ms	252932 KB	Output is correct
17	Correct	351 ms	142752 KB	Output is correct
18	Correct	350 ms	142828 KB	Output is correct
19	Correct	632 ms	258368 KB	Output is correct
20	Correct	580 ms	258392 KB	Output is correct