Submission #853250

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853250	2023-09-23T18:26:30 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	306 ms	162128 KB

apple

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;

struct Node {
	int l, r, sum, lazy;
	Node *ptrL, *ptrR;

	Node(int a, int b) : l(a), r(b), sum(0), lazy(0), ptrL(NULL), ptrR(NULL) { };
	void add() {
		if (ptrL == NULL && l != r) {
			int mid = (l + r) / 2;
			ptrL = new Node(l, mid);
			ptrR = new Node(mid+1, r);
		}
	}

	void push() {
		if (lazy) {
			sum = r - l + 1;
			if (l != r) {
				add();
				ptrL->lazy = 1;
				ptrR->lazy = 1;
			}
			lazy = 0;
		}
	}

	void update(int a, int b) {
		push();
		if (a <= l && r <= b) {
			lazy = 1;
			push();
			return ;
		}
		if (l > b || a > r)
			return ;
		add();
		ptrL->update(a, b);
		ptrR->update(a, b);
		sum = ptrL->sum + ptrR->sum; 
	}

	int query(int a, int b) {
		push();
		if (a <= l && r <= b)
			return sum;
		if (l > b || a > r)
			return 0;
		return (ptrL ? ptrL->query(a, b) : 0) + (ptrR ? ptrR->query(a, b) : 0);
	}
};

int main() {
	fast
	int M, D, X, Y;
	cin >> M;

	Node *root = new Node(1, 1e8);
	int C = 0;
	while (M--) {
		cin >> D >> X >> Y;
		X += C, Y += C;
		if (D == 1) {
			C = root->query(X, Y);
			cout << C << "\n";
		} else
			root->update(X, Y);
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	13 ms	8536 KB	Output is correct
5	Correct	15 ms	10328 KB	Output is correct
6	Correct	15 ms	9816 KB	Output is correct
7	Correct	15 ms	10328 KB	Output is correct
8	Correct	129 ms	75600 KB	Output is correct
9	Correct	280 ms	128436 KB	Output is correct
10	Correct	282 ms	144208 KB	Output is correct
11	Correct	291 ms	156752 KB	Output is correct
12	Correct	306 ms	162128 KB	Output is correct
13	Incorrect	54 ms	29260 KB	Output isn't correct
14	Halted	0 ms	0 KB	-