Submission #426702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426702	2021-06-14T09:18:22 Z	jeqcho	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	558 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;
	T 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()
	{
		extend();
		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)
	{
		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)
	{
		push();
		if(lq>=rx || rq<=lx)return;
		if(lq<=lx && rq>=rx)
		{
			lazy=v;
			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	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	20 ms	8556 KB	Output is correct
5	Correct	25 ms	10356 KB	Output is correct
6	Correct	24 ms	9932 KB	Output is correct
7	Correct	25 ms	10352 KB	Output is correct
8	Correct	209 ms	76948 KB	Output is correct
9	Correct	438 ms	130760 KB	Output is correct
10	Correct	439 ms	146808 KB	Output is correct
11	Correct	558 ms	159408 KB	Output is correct
12	Correct	479 ms	164676 KB	Output is correct
13	Correct	463 ms	205012 KB	Output is correct
14	Correct	499 ms	207208 KB	Output is correct
15	Runtime error	549 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-