Submission #1086380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086380	2024-09-10T11:32:49 Z	Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	681 ms	262144 KB

apple

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

//#define int long long
#define all(a) a.begin(), a.end()

#ifdef IS_LOCAL

#define dbg(x) {cout << #x << " = " << x << endl;}

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i];
		if (i != (int)v.size()-1)
			os << ", ";
	}
	os << "]";
	return os;
}

#else

#define dbg(x) 0

#endif

struct SegTree {
	struct Node {
		Node* L = NULL;
		Node* R = NULL;
		int v = 0;
		char lz = 0;
	};
	typedef Node* pnode;
	pnode R = NULL;
	int n;
	SegTree(int n_) {
		n = n_;
	}
	void destroy(pnode& r) {
		if (!r) return;
		destroy(r->L);
		destroy(r->R);
		delete r;
	}
	~SegTree() {
		destroy(R);
	}
	void push_lz(pnode& n, int l, int r) {
		if (!n) {
			n = new Node;
		}
		if (r-l <= 1) return;
		if (n->lz) {
			if (!n->L) {
				n->L = new Node;
			}
			if (!n->R) {
				n->R = new Node;
			}
			int m = (l+r)/2;
			n->lz = 0;
			n->L->lz = n->R->lz = 1;
			n->L->v = (m-l);
			n->R->v = (r-m);
		}
	}
	void update(pnode& R, int l, int r, int ql, int qr) {
		push_lz(R, l, r);
		if (ql <= l && r <= qr) {
			R->v = (r-l);
			R->lz = 1;
			return;
		}
		if (r <= ql || qr <= l || r == l) {
			return;
		}
		int m = (r+l)/2;
		update(R->L, l, m, ql, qr);
		update(R->R, m, r, ql, qr);
		R->v = R->L->v + R->R->v;
	}
	int query(pnode& R, int l, int r, int ql, int qr) {
		push_lz(R, l, r);
		if (ql <= l && r <= qr) {
			return R->v;
		}
		if (r <= ql || qr <= l || r == l) {
			return 0;
		}
		int m = (r+l)/2;
		return query(R->L, l, m, ql, qr)+
				query(R->R, m, r, ql, qr);
	}
	void set_1(int l, int r) {
		update(R, 0, n, l, r);
	}
	int get_sum(int l, int r) {
		return query(R, 0, n, l, r);
	}
};

signed main() {
	int M;
	cin >> M;
	int C = 0;
	SegTree st(1e9+1000);
	while (M--) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			C = st.get_sum(x+C-1, y+C);
			cout << C << endl;
		} else {
			st.set_1(x+C-1, y+C);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	436 KB	Output is correct
4	Correct	26 ms	5888 KB	Output is correct
5	Correct	27 ms	7260 KB	Output is correct
6	Correct	25 ms	7000 KB	Output is correct
7	Correct	26 ms	7112 KB	Output is correct
8	Correct	188 ms	52304 KB	Output is correct
9	Correct	378 ms	88344 KB	Output is correct
10	Correct	420 ms	99192 KB	Output is correct
11	Correct	407 ms	107600 KB	Output is correct
12	Correct	408 ms	111148 KB	Output is correct
13	Correct	426 ms	138460 KB	Output is correct
14	Correct	422 ms	139856 KB	Output is correct
15	Correct	625 ms	254548 KB	Output is correct
16	Correct	655 ms	256700 KB	Output is correct
17	Correct	448 ms	145424 KB	Output is correct
18	Correct	414 ms	145488 KB	Output is correct
19	Correct	666 ms	262144 KB	Output is correct
20	Correct	681 ms	262144 KB	Output is correct