Submission #887880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
887880	2023-12-15T12:13:19 Z	NintsiChkhaidze	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	402 ms	208040 KB

apple

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left t->l,l,(l + r)/2
#define right t->r,(l + r)/2 + 1,r
using namespace std;

const int inf = 1000000000;

struct Node {
    ll s,lz;
    Node *l, *r;
    Node() : s(0), lz(0), l(NULL), r(NULL) { }
};

void children(Node *t){
	if (!(t->l)) t->l = new Node();
	if (!(t->r)) t->r = new Node();
}
void push(Node *t,int l,int r){
	if ((t -> lz) == 0) return;

	int k = t -> lz;
	(t -> l) -> lz = k;
	(t -> l) -> s = (l + r)/2 - l + 1;
	
	(t -> r) -> lz = k;
	(t -> r) -> s = r - (l + r)/2;

	(t -> lz) = 0;
}

void upd(Node *t,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t -> s = (r - l + 1);
		t -> lz = 1;
		return;
	}

	if (!t->l) t->l = new Node();
	if (!t->r) t->r = new Node();

	children(t);
	push(t,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t->s = (t->l)->s + (t->r)->s;
}

int get(Node *t,int l,int r,int L,int R){
	if (t==NULL || r < L || R < l) return 0;
	if (L <= l && r <= R) return t->s;

	children(t);
	push(t,l,r);
	return get(left,L,R) + get(right,L,R);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int q,c = 0;
	cin>>q;

	Node *root = new Node();

	while (q--){
		int tp,l,r;
		cin>>tp>>l>>r;
		l += c;
		r += c;

		if (tp == 1){
			c = get(root,1,inf,l,r);
			cout<<c<<endl;
		}else{
			upd(root,1,inf,l,r);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	17 ms	4964 KB	Output is correct
5	Correct	18 ms	5980 KB	Output is correct
6	Correct	17 ms	5980 KB	Output is correct
7	Correct	18 ms	5988 KB	Output is correct
8	Correct	122 ms	44728 KB	Output is correct
9	Correct	251 ms	77396 KB	Output is correct
10	Correct	263 ms	85564 KB	Output is correct
11	Correct	268 ms	91728 KB	Output is correct
12	Correct	283 ms	94676 KB	Output is correct
13	Correct	256 ms	109908 KB	Output is correct
14	Correct	261 ms	111200 KB	Output is correct
15	Correct	402 ms	201916 KB	Output is correct
16	Correct	381 ms	203344 KB	Output is correct
17	Correct	262 ms	114772 KB	Output is correct
18	Correct	257 ms	114944 KB	Output is correct
19	Correct	377 ms	207696 KB	Output is correct
20	Correct	383 ms	208040 KB	Output is correct