Submission #694654

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
694654	2023-02-04T07:49:09 Z	clams	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	369 ms	139476 KB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second

const int M = 1e5 + 5;

int m;

struct Node {
	Node* le;
	Node* ri;
	int sum;
	bool lazy;
	
	Node() {
		le = ri = nullptr;
		sum = 0;
		lazy = false;
	}
	
	void extend() {
		if (!le) le = new Node();
		if (!ri) ri = new Node();
	}
};

Node* root;

void Down(Node* x, int lx, int rx, int mid) {
	if (!x->lazy) return;
	x->le->sum = mid - lx + 1;
	x->le->lazy = true;
	x->ri->sum = rx - mid;
	x->ri->lazy = true;
	x->lazy = false;
}

void Update(int l, int r, Node* x, int lx, int rx) {
	if (lx > r || rx < l) return;
	if (l <= lx && rx <= r) {
		x->sum = rx - lx + 1;
		x->lazy = true;
		return;
	}
	int mid = lx + (rx - lx) / 2;
	x->extend();
	Down(x, lx, rx, mid);
	Update(l, r, x->le, lx, mid);
	Update(l, r, x->ri, mid + 1, rx);
	x->sum = x->le->sum + x->ri->sum;
}

int Get(int l, int r, Node* x, int lx, int rx) {
	if (lx > r || rx < l) return 0;
	if (l <= lx && rx <= r)	return x->sum;
	int mid = lx + (rx - lx) / 2;
	x->extend();
	Down(x, lx, rx, mid);
	return Get(l, r, x->le, lx, mid) + Get(l, r, x->ri, mid + 1, rx);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> m;
	int c = 0;
	root = new Node();
	
	while (m--) {
		int d, x, y;
		cin >> d >> x >> y;
		
		x += c, y += c;
		
		if (d == 1) {
			int ans = Get(x, y, root, 1, (int)1e9);
			cout << ans << '\n';
			c = ans;	
		} else {
			Update(x, y, root, 1, (int)1e9);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	15 ms	3412 KB	Output is correct
5	Correct	12 ms	4180 KB	Output is correct
6	Correct	17 ms	3960 KB	Output is correct
7	Correct	19 ms	4104 KB	Output is correct
8	Correct	99 ms	30144 KB	Output is correct
9	Correct	205 ms	52280 KB	Output is correct
10	Correct	224 ms	57764 KB	Output is correct
11	Correct	225 ms	61876 KB	Output is correct
12	Correct	221 ms	63848 KB	Output is correct
13	Correct	208 ms	74204 KB	Output is correct
14	Correct	207 ms	74936 KB	Output is correct
15	Correct	324 ms	135476 KB	Output is correct
16	Correct	355 ms	136368 KB	Output is correct
17	Correct	224 ms	77508 KB	Output is correct
18	Correct	214 ms	77464 KB	Output is correct
19	Correct	340 ms	139476 KB	Output is correct
20	Correct	369 ms	139436 KB	Output is correct