Submission #1086377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086377	2024-09-10T11:27:37 Z	Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	500 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;
		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 || 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

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	348 KB	Output is correct
4	Correct	24 ms	9456 KB	Output is correct
5	Correct	33 ms	11600 KB	Output is correct
6	Correct	31 ms	11092 KB	Output is correct
7	Correct	34 ms	11428 KB	Output is correct
8	Correct	215 ms	87636 KB	Output is correct
9	Correct	447 ms	152148 KB	Output is correct
10	Correct	461 ms	168384 KB	Output is correct
11	Correct	489 ms	180820 KB	Output is correct
12	Correct	483 ms	186336 KB	Output is correct
13	Correct	500 ms	217260 KB	Output is correct
14	Correct	484 ms	219200 KB	Output is correct
15	Runtime error	372 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-