Submission #757220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757220	2023-06-12T19:19:31 Z	tcmmichaelb139	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	424 ms	262144 KB

apple

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

#pragma GCC optimize("Ofast,unroll-loops")

struct Node {
	int val;
	int lzAdd;
	int L, R;
	Node *c[2];
	Node(int l, int r) : L(l), R(r) {
		val = 0;
		lzAdd = 0;
		c[0] = c[1] = NULL;
	}
	void extend() {
		if (!c[0] && !c[1] && L != R) {
			int M = (L + R) / 2;
			c[0] = new Node(L, M);
			c[1] = new Node(M + 1, R);
		}
	}
	void push() {
		extend();
		if (lzAdd == 0) return;
		val = R - L + 1;
		if (L != R) {
			if (c[0]) c[0]->lzAdd = lzAdd;
			if (c[1]) c[1]->lzAdd = lzAdd;
		}
		lzAdd = 0;
	}
	void upd(int lo, int hi, int inc) {
		push();
		if (lo > R || L > hi) return;
		if (lo <= L && R <= hi) {
			lzAdd = inc;
			push();
			return;
		}
		c[0]->upd(lo, hi, inc);
		c[1]->upd(lo, hi, inc);
		val = c[0]->val + c[1]->val;
	}
	int query(int lo, int hi) {
		push();
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return val;
		int res = 0;
		res += c[0]->query(lo, hi);
		res += c[1]->query(lo, hi);
		return res;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	Node seg(1, 1'000'000'000);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			ans = seg.query(b + ans, c + ans);
			cout << ans << '\n';
		} else {
			seg.upd(b + ans, c + ans, 1);
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	16 ms	8504 KB	Output is correct
5	Correct	20 ms	10408 KB	Output is correct
6	Correct	20 ms	9940 KB	Output is correct
7	Correct	27 ms	10316 KB	Output is correct
8	Correct	193 ms	77048 KB	Output is correct
9	Correct	344 ms	130800 KB	Output is correct
10	Correct	416 ms	146864 KB	Output is correct
11	Correct	409 ms	159368 KB	Output is correct
12	Correct	389 ms	164872 KB	Output is correct
13	Correct	354 ms	205036 KB	Output is correct
14	Correct	424 ms	207092 KB	Output is correct
15	Runtime error	413 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-