Submission #587098

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587098	2022-07-01T10:00:12 Z	blue	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	205 ms	3008 KB

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;

		// cerr << l << ' ' << r << " -> " << "ripen " << L << ' ' << R << '\n';
		
		if(L <= l && r <= R)
		{
			// cerr << "case 1\n";
			lp = 1;
			ct = r-l+1;
		}
		else
		{
			// cerr << "case 2\n";
			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);
		}

		// cerr << l << ' ' << r << " : " << ct << ' ' << lp << '\n';
	}

	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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	476 KB	Output is correct
5	Correct	24 ms	488 KB	Output is correct
6	Correct	17 ms	484 KB	Output is correct
7	Correct	17 ms	484 KB	Output is correct
8	Correct	89 ms	1364 KB	Output is correct
9	Correct	205 ms	2400 KB	Output is correct
10	Correct	164 ms	2420 KB	Output is correct
11	Correct	181 ms	2468 KB	Output is correct
12	Correct	172 ms	2372 KB	Output is correct
13	Correct	188 ms	2772 KB	Output is correct
14	Correct	184 ms	2728 KB	Output is correct
15	Correct	186 ms	2996 KB	Output is correct
16	Correct	193 ms	2980 KB	Output is correct
17	Correct	193 ms	2852 KB	Output is correct
18	Correct	202 ms	2808 KB	Output is correct
19	Correct	200 ms	2972 KB	Output is correct
20	Correct	203 ms	3008 KB	Output is correct