제출 #587098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587098		blue	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	205 ms	3008 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;

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