Submission #889064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889064	2023-12-18T18:18:55 Z	shadow_sami	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	75 ms	46740 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<=1e6);
	}
}

Subtask #1

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	14 ms	4956 KB	Output is correct
5	Correct	21 ms	5972 KB	Output is correct
6	Correct	17 ms	5724 KB	Output is correct
7	Correct	18 ms	5912 KB	Output is correct
8	Runtime error	75 ms	46740 KB	Execution killed with signal 6
9	Halted	0 ms	0 KB	-