Submission #1182372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182372		amcbn	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	455 ms	327680 KiB

apple

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

struct Vertex {
	int count = 0, l = 0, r = 0;
	bool lazy = false;
	Vertex* left = nullptr, * right = nullptr;
	Vertex() {

	}
	Vertex(int l, int r) : l(l), r(r) {

	}
	friend void makeSons(Vertex* vtx) {
		if (vtx->left == nullptr) {
			vtx->left = new Vertex(vtx->l, (vtx->l + vtx->r) / 2);
		}
		if (vtx->right == nullptr) {
			vtx->right = new Vertex((vtx->l + vtx->r) / 2 + 1, vtx->r);
		}
	}
	friend void pullSons(Vertex* vtx) {
		vtx->count = 0;
		if (vtx->left) {
			vtx->count += vtx->left->count;
		}
		if (vtx->right) {
			vtx->count += vtx->right->count;
		}
	}
};

void propagate(Vertex* vtx) {
	if (vtx == nullptr || !vtx->lazy) {
		return;
	}
	vtx->count = vtx->r - vtx->l + 1;
	if (vtx->l != vtx->r) {
		makeSons(vtx);
		vtx->left->lazy = true;
		vtx->right->lazy = true;
	}
	vtx->lazy = false;
}

void update(Vertex* vtx, int ql, int qr) {
	propagate(vtx);
	if (vtx == nullptr || vtx->r < ql || qr < vtx->l) {
		return;
	}
	if (ql <= vtx->l && vtx->r <= qr) {
		vtx->lazy = true;
		propagate(vtx);
		return;
	}
	makeSons(vtx);
	update(vtx->left, ql, qr);
	update(vtx->right, ql, qr);
	pullSons(vtx);
}

int query(Vertex* vtx, int ql, int qr) {
	propagate(vtx);
	if (vtx == nullptr || vtx->r < ql || qr < vtx->l) {
		return 0;
	}
	if (ql <= vtx->l && vtx->r <= qr) {
		return vtx->count;
	}
	return query(vtx->left, ql, qr) + query(vtx->right, ql, qr);
}

const int max_coordinate = 1e9;
const int mmax = 1e5;
int M;

int main() {
	Vertex* root = new Vertex(1, max_coordinate);
	cin >> M;
	int C = 0;
	for (int i = 1; i <= M; ++i) {
		int t, x, y;
		cin >> t >> x >> y;
		x += C, y += C;
		if (t == 1) {
			cout << (C = query(root, x, y)) << "\n";
		}
		else {
			update(root, x, y);
		}
	}
}

• Subtask 1: 0 / 100