Submission #426726

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426726	2021-06-14T09:26:56 Z	jeqcho	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	578 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

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int m;
	cin>>m;
	int c=0;
	node<int>seg({0,(int)1e9+3});
	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,1);
		}
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	244 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	29 ms	8524 KB	Output is correct
5	Correct	26 ms	10284 KB	Output is correct
6	Correct	25 ms	9992 KB	Output is correct
7	Correct	25 ms	10308 KB	Output is correct
8	Correct	278 ms	76940 KB	Output is correct
9	Correct	477 ms	130784 KB	Output is correct
10	Correct	517 ms	146736 KB	Output is correct
11	Correct	552 ms	159508 KB	Output is correct
12	Correct	514 ms	164724 KB	Output is correct
13	Correct	511 ms	204992 KB	Output is correct
14	Correct	500 ms	207232 KB	Output is correct
15	Runtime error	578 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-