Submission #1000868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000868	2024-06-18T10:36:19 Z	aykhn	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	284 ms	118880 KB

apple

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

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

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

int m, c = 1;
vector<Node> st(2, {0, -1, -1});
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 == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	if (st[x].r == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	lz[(st[x].l == -1 ? st[x].l = ++c : st[x].l)] = lz[(st[x].r == -1 ? st[x].r = ++c : st[x].r)] = lz[x];
	lz[x] = -1;
}
void make(int l, int r, int x, int lx, int rx)
{
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] = 1;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	if (st[x].l == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	if (st[x].r == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	make(l, mid, (st[x].l == -1 ? st[x].l = ++c : st[x].l), lx, rx);
	make(mid + 1, r, (st[x].r == -1 ? st[x].r = ++c : st[x].r), lx, rx);
	st[x].val = (st[x].l != -1 ? st[st[x].l].val : 0) + (st[x].r != -1 ? st[st[x].r].val : 0);
}
int get(int l, int r, int x, int lx, int rx)
{
	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 (st[x].l != -1 ? get(l, mid, st[x].l, lx, rx) : 0) + (st[x].r != -1 ? get(mid + 1, r, st[x].r, lx, rx) : 0);
}

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

Compilation message

apple.cpp: In function 'void relax(int, int, int)':
apple.cpp:39:32: warning: operation on 'c' may be undefined [-Wsequence-point]
   39 |  lz[(st[x].l == -1 ? st[x].l = ++c : st[x].l)] = lz[(st[x].r == -1 ? st[x].r = ++c : st[x].r)] = lz[x];
      |                                ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	4836 KB	Output is correct
5	Correct	12 ms	5092 KB	Output is correct
6	Correct	12 ms	4320 KB	Output is correct
7	Correct	13 ms	4324 KB	Output is correct
8	Correct	74 ms	32116 KB	Output is correct
9	Correct	167 ms	61844 KB	Output is correct
10	Correct	173 ms	59800 KB	Output is correct
11	Correct	177 ms	61084 KB	Output is correct
12	Correct	175 ms	59552 KB	Output is correct
13	Correct	161 ms	63368 KB	Output is correct
14	Correct	160 ms	64220 KB	Output is correct
15	Correct	262 ms	117388 KB	Output is correct
16	Correct	263 ms	117900 KB	Output is correct
17	Correct	170 ms	66436 KB	Output is correct
18	Correct	167 ms	66184 KB	Output is correct
19	Correct	277 ms	118880 KB	Output is correct
20	Correct	284 ms	118000 KB	Output is correct