Submission #1129483

#TimeUsernameProblemLanguageResultExecution timeMemory
1129483hamzabcMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
47 ms916 KiB
#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


class tree{
	private:
		struct node{
			long long int data = 0;
			node* l = nullptr,* r = nullptr;
		};
		node* root = nullptr;
		void _add(long long int l, long long int r, long long int tl, long long int tr, node* &rt){
			if (l > tr || tl > r)
				return;
			if (!rt){
				rt = new node;
			}
			if (rt->data == tr - tl + 1)
				return;
			if (l <= tl && tr <= r){
				rt->data = tr - tl + 1;
				return;
			}
			long long int mid = (tl + tr) >> 1;
			_add(l, r, tl, mid, rt->l);
			_add(l, r, mid + 1, tr, rt->r);
			rt->data = 0;
			if (rt->l)
				rt->data += rt->l->data;
			if (rt->r)
				rt->data += rt->r->data;
		}
		long long int _count(long long int l, long long int r, long long int tl, long long int tr, node* &rt){
			if (l > tr || tl > r)
				return 0;
			if (!rt){
				return 0;
			}
			if (rt->data == tr - tl + 1)
				return min(r, tr) - max(l, tl) + 1;
			if (l <= tl && tr <= r){
				return rt->data;
			}
			long long int mid = (tl + tr) >> 1;
			return _count(l, r, tl, mid, rt->l) + _count(l, r, mid + 1, tr, rt->r);
		}
	public:
		void add(long long int l, long long int r){
			_add(l, r, 0, 1e9, root);
		}
		long long int count(long long int l, long long int r){
			return _count(l, r, 0, 1e9, root);
		}
};


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tree segtre;
	long long int Q;
	cin >> Q;
	long long int C = 0;
	while (Q--){
		long long int D, X, Y;
		cin >> D >> X >> Y;
		X += C;
		Y += C;
		if (D - 1){
			segtre.add(X, Y);
		}else{
			C = segtre.count(X, Y);
			cout << C endl;
		}
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...