Submission #890264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
890264	2023-12-20T21:30:24 Z	Justin1	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	356 ms	262144 KB

apple

#include <bits/stdc++.h>
#define f first
#define s second
// #define int long long
using namespace std;
 
struct dynamicSeg { //range max query, range set update
	int val;
	bool lzy;
	int l, r;
	dynamicSeg *L = NULL, *R = NULL;
	inline void extend(dynamicSeg *&node, int l, int r) {
		if (node == NULL) node = new dynamicSeg(l, r);
	}
	inline void push() {
		if (!lzy) return;
		int mid = (this->l + this->r) / 2;
		extend(L, this->l, mid), extend(R, mid + 1, this->r);
		L-> val = L->r - L->l + 1;
		R-> val = R->r - R->l + 1;
		L-> lzy = R->lzy = !(lzy = 0);
	}
	dynamicSeg (int sz) : l(1), r(sz) {}
	dynamicSeg (int l, int r) : l(l), r(r) {}
	inline void upd(int l, int r) {
		push();
		if (this->r < l || r < this->l) return;
		if (l <= this->l && this->r <= r) {
			val = this->r - this->l + 1;
			lzy = 1;
			return;
		}
		int mid = (this->l + this->r) / 2;
		extend(L, this->l, mid), extend(R, mid + 1, this->r);
		L->upd(l, r), R->upd(l, r);
		val = L->val + R->val;
	}
	inline int qry(int l, int r) {
		push();
		if (this->r < l || r < this->l) return 0;
		if (l <= this->l && this->r <= r) return val;
		return (L ? L->qry(l, r) : 0) + (R ? R->qry(l, r) : 0);
	}
};
 
int n, m, k, x, y, z;
dynamicSeg seg(1'000'000'000);
 
void solve() {
	int C = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y >> z;
		if (x == 1) cout << (C = seg.qry(y + C, z + C)) << "\n"; 
		else seg.upd(y + C, z + C);
	}
}
 
signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    cout << fixed << setprecision(10);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	400 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	9420 KB	Output is correct
5	Correct	17 ms	11356 KB	Output is correct
6	Correct	17 ms	11096 KB	Output is correct
7	Correct	21 ms	11352 KB	Output is correct
8	Correct	147 ms	86872 KB	Output is correct
9	Correct	314 ms	150680 KB	Output is correct
10	Correct	309 ms	166736 KB	Output is correct
11	Correct	333 ms	179332 KB	Output is correct
12	Correct	356 ms	184912 KB	Output is correct
13	Correct	303 ms	215376 KB	Output is correct
14	Correct	298 ms	217096 KB	Output is correct
15	Runtime error	330 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-