Submission #1086375

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086375	2024-09-10T11:22:12 Z	Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	498 ms	262144 KB

apple

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

#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;
		int 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 (!n->L) {
			n->L = new Node;
		}
		if (!n->R) {
			n->R = new Node;
		}
		int m = (l+r)/2;
		if (n->lz) {
			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) {
			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) {
			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);
	}
};

int 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	21 ms	6448 KB	Output is correct
5	Correct	27 ms	7764 KB	Output is correct
6	Correct	26 ms	7588 KB	Output is correct
7	Correct	26 ms	7784 KB	Output is correct
8	Correct	199 ms	58852 KB	Output is correct
9	Correct	406 ms	102224 KB	Output is correct
10	Correct	419 ms	113232 KB	Output is correct
11	Correct	422 ms	121452 KB	Output is correct
12	Correct	464 ms	124996 KB	Output is correct
13	Correct	428 ms	145976 KB	Output is correct
14	Correct	429 ms	147028 KB	Output is correct
15	Runtime error	498 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-