Submission #993896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993896	2024-06-06T18:41:42 Z	beaboss	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	522 ms	262144 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) {
	cur->sm = cur->l->sm + cur->r->sm;
}

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

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

		return cur->sm;
	}

	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

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	18 ms	6492 KB	Output is correct
5	Correct	21 ms	7768 KB	Output is correct
6	Correct	21 ms	7504 KB	Output is correct
7	Correct	21 ms	7760 KB	Output is correct
8	Correct	164 ms	58964 KB	Output is correct
9	Correct	299 ms	102432 KB	Output is correct
10	Correct	319 ms	112976 KB	Output is correct
11	Correct	335 ms	121316 KB	Output is correct
12	Correct	337 ms	125008 KB	Output is correct
13	Correct	324 ms	145744 KB	Output is correct
14	Correct	315 ms	147284 KB	Output is correct
15	Runtime error	522 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-