Submission #1091140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091140		4QT0R	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	299 ms	209544 KiB

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 / 100