Submission #586912

#	Time	Username	Problem	Language	Result	Execution time	Memory
586912		blue	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KiB

apple

#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);
		}
	}
}

• Subtask 1: 0 / 100