Submission #1181410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181410		Drew_	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	324 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 1e9;

struct Node
{
	int val, lz;
	Node *lt, *rt;

	Node() : val(0), lz(0), lt(nullptr), rt(nullptr) {}
};

Node* root = new Node();
inline void propagate(Node* &node, int l, int r)
{
	if (node->lz)
	{
		node->val += (r-l+1) * node->lz;
		if (l < r)
		{
			if (!node->lt) node->lt = new Node();
			node->lt->lz += node->lz;
			
			if (!node->rt) node->rt = new Node();
			node->rt->lz += node->lz;
		}
		node->lz = 0;
	}
}

inline int query(int p, int q, Node* &node = root, int l = 1, int r = MAX) 
{
	if (!node) return 0;

	propagate(node, l, r);
	if (l > q || r < p)
		return 0;
	if (p <= l && r <= q)
		return node->val;
	int mid = (l + r) >> 1;
	return query(p, q, node->lt, l, mid) + query(p, q, node->rt, mid+1, r);
}

inline void add(int p, int q, int val, Node* &node = root, int l = 1, int r = MAX)
{
	if (!node) node = new Node();

	propagate(node, l, r);
	if (l > q || r < p)
		return;
	if (p <= l && r <= q)
	{
		node->lz += val;
		propagate(node, l, r);
		return;
	}

	int mid = (l + r) >> 1;
	add(p, q, val, node->lt, l, mid);
	add(p, q, val, node->rt, mid+1, r);
	node->val = node->lt->val + node->rt->val; 
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);

	int N, C = 0;
	cin >> N;

	set<ii> st;
	for (int i = 0; i < N; ++i)
	{
		int D, L, R;
		cin >> D >> L >> R;

		L += C; R += C;
		if (D == 1) 
		{
			int Z = query(L, R);

			cout << Z << '\n';
			C += Z;
		}	
		else
		{
			// find all intervals in st that intersects with [L, R]
			const auto isect = [](int l, int r, int p, int q) -> bool
			{
				return !(l > q || r < p);
			};	

			auto it = st.lower_bound({L, 0});
			if (it != st.begin()) it = prev(it);
			if (it != st.end() && !isect(it->f1, it->s2, L, R)) it = next(it);
			
			for (; it != st.end() && isect(it->f1, it->s2, L, R); it = st.erase(it))
			{
				add(it->f1, it->s2, -1);
				L = min(L, it->f1); R = max(R, it->s2);
			}
			add(L, R, 1);
			st.insert({L, R});
		}
	}

	return 0;
}

• Subtask 1: 0 / 100