Submission #1000936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000936	2024-06-18T11:32:26 Z	aykhn	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	264 ms	117644 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	4324 KB	Output is correct
5	Correct	13 ms	4344 KB	Output is correct
6	Correct	13 ms	4324 KB	Output is correct
7	Correct	12 ms	4324 KB	Output is correct
8	Correct	77 ms	32440 KB	Output is correct
9	Correct	168 ms	59556 KB	Output is correct
10	Correct	180 ms	60448 KB	Output is correct
11	Correct	170 ms	61336 KB	Output is correct
12	Correct	176 ms	62592 KB	Output is correct
13	Correct	178 ms	62516 KB	Output is correct
14	Correct	174 ms	63124 KB	Output is correct
15	Correct	260 ms	117644 KB	Output is correct
16	Correct	264 ms	116732 KB	Output is correct
17	Correct	171 ms	65284 KB	Output is correct
18	Correct	168 ms	65664 KB	Output is correct
19	Correct	262 ms	117640 KB	Output is correct
20	Correct	253 ms	117076 KB	Output is correct