Submission #1000936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000936		aykhn	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	264 ms	117644 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

struct Node
{
	int val = 0, l = 0, r = 0;
};

const int MXN = 1e5 + 5;
const int mod = 1e9 + 7;
const int LOG = 31;

int m, c = 1;
vector<Node> st(2, {0, 0, 0});
vector<int> lz(2, -1);

void relax(int l, int r, int x)
{
	if (lz[x] == -1) return;
	st[x].val = (r - l + 1);
	if (l == r) 
	{
		lz[x] = -1;
		return;
	}
	if (!st[x].l)
	{
		lz.push_back(-1);
		st.push_back({0, 0, 0});
		st[x].l = ++c;
	}
	if (!st[x].r)
	{
		lz.push_back(-1);
		st.push_back({0, 0, 0});
		st[x].r = ++c;
	}
	lz[st[x].l] = lz[st[x].r] = lz[x];
	lz[x] = -1;
}
int make(int l, int r, int x, int lx, int rx)
{
	if (!x) x = ++c;
	relax(l, r, x);
	if (l > rx || r < lx) return x;
	if (l >= lx && r <= rx)
	{
		lz[x] = 1;
		relax(l, r, x);
		return x;
	}
	int mid = (l + r) >> 1;
	if (!st[x].l)
	{
		lz.push_back(-1);
		st.push_back({0, 0, 0});
	}
	if (!st[x].r)
	{
		lz.push_back(-1);
		st.push_back({0, 0, 0});
	}
	st[x].l = make(l, mid, st[x].l, lx, rx);
	st[x].r = make(mid + 1, r, st[x].r, lx, rx);
	st[x].val = st[st[x].l].val + st[st[x].r].val;
	return x;
}
int get(int l, int r, int x, int lx, int rx)
{
	if (!x) return 0;
	if (l > rx || r < lx) return 0;
	relax(l, r, x);
	if (l >= lx && r <= rx) return st[x].val; 
	int mid = (l + r) >> 1;
	return get(l, mid, st[x].l, lx, rx) + get(mid + 1, r, st[x].r, lx, rx);
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> m;
	int p = 0;
	while (m--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			int l, r;
			cin >> l >> r;
			l += p, r += p;
			cout << (p = get(1, 1e9, 1, l, r)) << '\n';
		}
		else
		{
			int l, r;
			cin >> l >> r;
			l += p, r += p;
			make(1, 1e9, 1, l, r);
		}
	}
}

• Subtask 1: 100 / 100