Submission #1091140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091140	2024-09-19T22:57:11 Z	4QT0R	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	299 ms	209544 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct node{
	node* lft;
	node* rght;
	ll l;
	ll p;
	ll sm;
};

node* head=new node;

ll sum(node* now, ll a, ll b){
	if (now->p < a || b < now->l){
		return 0;
	}
	if (a <= now->l && now->p <= b){
		return now->sm;
	}
	if ((now->p - now->l + 1) == now->sm){
		if (!(now->lft)){
			now->lft=new node;
			now->lft->l=now->l;
			now->lft->p=(now->l+now->p)/2;
			now->lft->lft=nullptr;
			now->lft->rght=nullptr;
		}
		if (!(now->rght)){
			now->rght=new node;
			now->rght->l=(now->l+now->p)/2+1;
			now->rght->p=now->p;
			now->rght->lft=nullptr;
			now->rght->rght=nullptr;
		}
		now->lft->sm=now->sm/2;
		now->rght->sm=now->sm/2;
	}
	return (now->lft?sum(now->lft,a,b):0)+(now->rght?sum(now->rght,a,b):0);
}

void add(node* now, ll a, ll b){
	if (now->p < a || b < now->l)return;
	if (a <= now->l && now->p <= b){
		now->sm=(now->p - now->l + 1);
		return;
	}
	if (!(now->lft)){
		now->lft=new node;
		now->lft->l=now->l;
		now->lft->p=(now->l+now->p)/2;
		now->lft->sm=0;
		now->lft->lft=nullptr;
		now->lft->rght=nullptr;
	}
	if (!(now->rght)){
		now->rght=new node;
		now->rght->l=(now->l+now->p)/2+1;
		now->rght->p=now->p;
		now->rght->sm=0;
		now->rght->lft=nullptr;
		now->rght->rght=nullptr;
	}
	if ((now->p - now->l + 1) == now->sm){
		now->lft->sm=now->sm/2;
		now->rght->sm=now->sm/2;
	}
	add(now->lft,a,b);
	add(now->rght,a,b);
	now->sm=now->lft->sm + now->rght->sm;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll m;
	cin >> m;
	head->l=0;
	head->p=INT_MAX>>1;
	head->sm=0;
	head->lft=nullptr;
	head->rght=nullptr;
	ll d,a,b,c=0;
	for (ll i = 1; i<=m; i++){
		cin >> d >> a >> b;
		if (d==1){
			c=sum(head,a+c,b+c);
			cout << c << '\n';
		}
		else{
			add(head,a+c,b+c);
		}
	}
}

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	9 ms	5212 KB	Output is correct
5	Correct	11 ms	6488 KB	Output is correct
6	Correct	10 ms	5936 KB	Output is correct
7	Correct	10 ms	6212 KB	Output is correct
8	Correct	82 ms	45396 KB	Output is correct
9	Correct	184 ms	76904 KB	Output is correct
10	Correct	188 ms	86608 KB	Output is correct
11	Correct	191 ms	93004 KB	Output is correct
12	Correct	203 ms	95828 KB	Output is correct
13	Correct	176 ms	110932 KB	Output is correct
14	Correct	186 ms	111916 KB	Output is correct
15	Correct	299 ms	203608 KB	Output is correct
16	Correct	287 ms	204928 KB	Output is correct
17	Correct	176 ms	115792 KB	Output is correct
18	Correct	173 ms	115792 KB	Output is correct
19	Correct	294 ms	209492 KB	Output is correct
20	Correct	282 ms	209544 KB	Output is correct