Submission #647594

#	Time	Username	Problem	Language	Result	Execution time	Memory
647594		ymm	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	44 ms	2636 KiB

apple

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1e7+10;

struct node {
	int cnt;
	int l, r;
} seg[100'000'000];

int rt;

int new_node()
{
	static int nxt = 1;
	return nxt++;
}

void up(int i)
{
	seg[i].cnt =   (seg[i].l? seg[seg[i].l].cnt: 0)
	             + (seg[i].r? seg[seg[i].r].cnt: 0);
}

void seg_set(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r) {
		seg[i].cnt = e-b;
		return;
	}
	if (r <= b || e <= l || seg[i].cnt == e-b)
		return;
	if (!seg[i].l)
		seg[i].l = new_node();
	if (!seg[i].r)
		seg[i].r = new_node();
	seg_set(l, r, seg[i].l, b, (b+e)/2);
	seg_set(l, r, seg[i].r, (b+e)/2, e);
	up(i);
}

int seg_get(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r)
		return seg[i].cnt;
	if (r <= b || e <= l || seg[i].cnt == 0)
		return 0;
	if (seg[i].cnt == e-b)
		return min(e, r) - max(b, l);
	return   seg_get(l,r,seg[i].l,b,(b+e)/2)
	       + seg_get(l,r,seg[i].r,(b+e)/2,e);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	rt = new_node();
	int C = 0;
	int q;
	cin >> q;
	while (q--) {
		int d, l, r;
		cin >> d >> l >> r;
		l += C-1; r += C;
		if (d == 1) {
			int x = seg_get(l, r, rt, 0, N);
			C = x;
			cout << x << '\n';
		} else {
			seg_set(l, r, rt, 0, N);
		}
	}
}

• Subtask 1: 0 / 100