Submission #889065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889065	2023-12-18T18:19:14 Z	shadow_sami	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	399 ms	207700 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;
 ll cnt = 0;
struct Node {
    ll s,lz;
    Node *l, *r;
    Node() : s(0), lz(0), l(NULL), r(NULL) { }
};
 
void children(Node *t){
	cnt++;
	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);

		}
		assert(cnt<=1e7);
	}
}

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	1 ms	348 KB	Output is correct
4	Correct	14 ms	4932 KB	Output is correct
5	Correct	18 ms	5980 KB	Output is correct
6	Correct	17 ms	5720 KB	Output is correct
7	Correct	23 ms	5976 KB	Output is correct
8	Correct	118 ms	43824 KB	Output is correct
9	Correct	260 ms	76028 KB	Output is correct
10	Correct	262 ms	83540 KB	Output is correct
11	Correct	258 ms	89968 KB	Output is correct
12	Correct	272 ms	92844 KB	Output is correct
13	Correct	246 ms	108112 KB	Output is correct
14	Correct	254 ms	109080 KB	Output is correct
15	Correct	369 ms	201620 KB	Output is correct
16	Correct	390 ms	203112 KB	Output is correct
17	Correct	266 ms	114772 KB	Output is correct
18	Correct	257 ms	114744 KB	Output is correct
19	Correct	369 ms	207616 KB	Output is correct
20	Correct	399 ms	207700 KB	Output is correct