Submission #993899

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993899	2024-06-06T18:44:12 Z	beaboss	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	356 ms	139348 KB

apple

#include "bits/stdc++.h"

using namespace std;

const int MX = 1e9 + 10;

#define FOR(i, a, b) for (int i = a; i < b; i++)

struct node {
	int sm, lz;
	node *l, *r;
};
 
node* root;

void down(node *&cur, int l, int m, int r) {
	if (!cur->lz) return;
	if (cur->l == nullptr) cur->l = new node();
	if (cur->r == nullptr) cur-> r = new node();

	cur->l->sm = (m - l);
	cur->r->sm = (r - m);
	cur->l->lz = 1;
	cur->r->lz = 1;

	cur->lz = 0;
}

void up(node *&cur) {
	int res = 0;
	if (cur->l != nullptr) res += cur->l->sm;
	if (cur->r != nullptr) res += cur->r->sm;

	cur->sm = res;
}

void update(int ul, int ur, node *&cur = root, int l = 0, int r = MX) {
		
	
	
	if (ur <= l || ul >= r) return;
	if (cur == nullptr) cur = new node();
	if (ul <= l && ur >= r) {
		// cout << l << r << endl;
		cur->sm = r-l;
		cur->lz = 1;
		// cout << l << r <<
		return;
	}

	
	down(cur, l, (l + r) / 2, r);

	int m = (l + r) / 2;
	update(ul, ur, cur->l, l, m);
	update(ul, ur, cur->r, m, r);

	up(cur);
}

int query(int ql, int qr, node *&cur = root, int l = 0, int r = MX) {

	if (qr <= l || ql >= r) return 0;
	if (cur == nullptr) return 0;
	if (ql <= l && qr >= r) {
		// cout << l << ' ' << r << ' ' << cur->sm << endl;

		return cur->sm;
	}

	
	
	down(cur, l, (l + r) / 2, r);

	int m = (l + r) / 2;
	return query(ql, qr, cur->l, l, m) + query(ql, qr, cur->r, m, r);
}


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

	int n;
	cin >> n;
	int c = 0;
	FOR(i, 0, n) {
		int t, x, y;
		cin >> t >> x >> y;

		if (t == 1) {
			c = query(x + c, y + 1 + c);
			cout << c << endl;
		} else {
			update(x + c, y + 1 + c);
		}
	}

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	3456 KB	Output is correct
5	Correct	15 ms	4184 KB	Output is correct
6	Correct	15 ms	4188 KB	Output is correct
7	Correct	16 ms	4188 KB	Output is correct
8	Correct	104 ms	30204 KB	Output is correct
9	Correct	218 ms	52304 KB	Output is correct
10	Correct	240 ms	57780 KB	Output is correct
11	Correct	217 ms	62032 KB	Output is correct
12	Correct	217 ms	63824 KB	Output is correct
13	Correct	216 ms	74388 KB	Output is correct
14	Correct	230 ms	75124 KB	Output is correct
15	Correct	313 ms	135540 KB	Output is correct
16	Correct	308 ms	136536 KB	Output is correct
17	Correct	230 ms	77384 KB	Output is correct
18	Correct	222 ms	77420 KB	Output is correct
19	Correct	356 ms	139348 KB	Output is correct
20	Correct	327 ms	139348 KB	Output is correct