Submission #426775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426775	2021-06-14T09:46:47 Z	jeqcho	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	570 ms	262148 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!=1e4);
		}
	}
	void push()
	{
		if(!lazy)return;
		val=rx-lx;
		lazy=0;
		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;
		push();
		if(lq<=lx && rq>=rx)return val;
		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

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	22 ms	7772 KB	Output is correct
5	Correct	25 ms	9524 KB	Output is correct
6	Correct	28 ms	9080 KB	Output is correct
7	Correct	27 ms	9420 KB	Output is correct
8	Correct	218 ms	71228 KB	Output is correct
9	Correct	410 ms	118660 KB	Output is correct
10	Correct	452 ms	136252 KB	Output is correct
11	Correct	532 ms	147412 KB	Output is correct
12	Correct	455 ms	152268 KB	Output is correct
13	Correct	427 ms	183620 KB	Output is correct
14	Correct	417 ms	185844 KB	Output is correct
15	Runtime error	570 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-