Submission #791302

# Submission time Handle Problem Language Result Execution time Memory
791302 2023-07-24T00:53:28 Z lukehsiao Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
1 ms 316 KB
#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);
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -