Submission #791302

#	Time	Username	Problem	Language	Result	Execution time	Memory
791302		lukehsiao	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	316 KiB

apple

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

struct node {
	int sum;
	bool lz;
	node* c[2];
	node() {
		sum = 0;
		lz = false;
		c[0] = c[1] = NULL;
	}
	void push(int l, int mid, int r) {
		if (lz) {
			c[0]->sum = mid-l+1;
			c[1]->sum = r-mid;
			c[0]->lz = c[1]->lz = true;
			lz = false;
		}
	}
	void upd(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			sum = r-l+1;
			lz = true;
		} else {
			int mid = (l+r)/2;
			if (!c[0]) c[0] = new node();
			if (!c[1]) c[1] = new node();
			push(l, mid, r);
			c[0]->upd(a, b, l, mid);
			c[1]->upd(a, b, mid+1, r);
			sum = c[0]->sum + c[1]->sum;
		}
	}
	int qry(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return sum;
		int mid = (l+r)/2;
		if (!c[0]) c[0] = new node();
		if (!c[1]) c[1] = new node();
		push(l, mid, r);
		return c[0]->qry(a, b, l, mid) + c[1]->qry(a, b, mid+1, r);
	}
};

ll m, c;

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

	node root = node();

	cin >> m;
	for (ll i=0, d, x, y; i<m; ++i) {
		cin >> d >> x >> y;
		if (d == 1) {
			int cnt = root.qry(x+c-1, y+c-1);
			c += cnt;
			cout << cnt << '\n';
		} else {
			root.upd(x+c-1, y+c-1);
		}
	}
}

• Subtask 1: 0 / 100