Submission #853248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853248	2023-09-23T18:23:14 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	312 ms	164692 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, 1e7);
	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	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	13 ms	8696 KB	Output is correct
5	Correct	15 ms	10332 KB	Output is correct
6	Correct	15 ms	9896 KB	Output is correct
7	Correct	15 ms	10336 KB	Output is correct
8	Correct	132 ms	76880 KB	Output is correct
9	Correct	280 ms	130912 KB	Output is correct
10	Correct	300 ms	146660 KB	Output is correct
11	Correct	312 ms	159240 KB	Output is correct
12	Correct	302 ms	164692 KB	Output is correct
13	Incorrect	27 ms	3928 KB	Output isn't correct
14	Halted	0 ms	0 KB	-