Submission #694654

#	Time	Username	Problem	Language	Result	Execution time	Memory
694654		clams	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	369 ms	139476 KiB

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 / 100