Submission #1086379

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

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	604 KB	Output is correct
4	Correct	21 ms	6612 KB	Output is correct
5	Correct	27 ms	7852 KB	Output is correct
6	Correct	25 ms	7768 KB	Output is correct
7	Correct	26 ms	7716 KB	Output is correct
8	Correct	196 ms	58960 KB	Output is correct
9	Correct	390 ms	102224 KB	Output is correct
10	Correct	416 ms	113208 KB	Output is correct
11	Correct	439 ms	121524 KB	Output is correct
12	Correct	432 ms	124956 KB	Output is correct
13	Correct	434 ms	145564 KB	Output is correct
14	Correct	433 ms	146768 KB	Output is correct
15	Runtime error	533 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-