Submission #1000868

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

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 (stderr)

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