Submission #586912

#TimeUsernameProblemLanguageResultExecution timeMemory
586912blueMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
1 ms212 KiB
#include <iostream>
#include <vector>
using namespace std;

const int inf = 1'000'000'000;

struct segtree
{
	int l = 0;
	int r = inf;

	int ct = 0;
	bool lp = 0;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
	}

	void ripen(int L, int R)
	{
		if(lp) return;
		if(R < l || r < L)
			return;
		else if(L <= l && r <= R)
		{
			lp = 1;
			ct = r-l+1;
		}
		else
		{
			if(left == NULL)
			{
				left = new segtree(l, (l+r)/2);
				left->ripen(L, R);
			}
			if(right == NULL)
			{
				right = new segtree((l+r)/2+1, r);
				right->ripen(L, R);
			}
			ct = (left != NULL ? left->ct : 0) + (right != NULL ? right->ct : 0);
		}
	}

	int count(int L, int R)
	{
		if(R < l || r < L)
			return 0;
		else if(L <= l && r <= R)
			return ct;
		else if(lp)
			return min(R,r) - max(L,l) + 1;
		else
		{
			int res = 0;
			if(left != NULL)
				res += left->count(L, R);
			if(right != NULL)
				res += right->count(L, R);
			return res;
		}
	}
};

int main()
{
	int M;
	cin >> M;

	segtree S;

	int c = 0;

	for(int j = 1; j <= M; j++)
	{
		int d, x, y;
		cin >> d >> x >> y;
		x += c;
		y += c;

		if(d == 1)
		{
			int z = S.count(x, y);
			cout << z << '\n';
			c = z;
		}
		else
		{
			S.ripen(x, y);
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...