Submission #688636

#	Time	Username	Problem	Language	Result	Execution time	Memory
688636		asdf1234coding	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	12 ms	10024 KiB

apple

#include <bits/stdc++.h>

#define int long long
using namespace std;

struct Node {
	int ans, lazy, tl, tr, l, r; //lzset
	Node() : ans(0), lazy(0), l(-1), r(-1) {}
};

#define MAXN 100009
Node st[MAXN];
int cnt = 2; //scuffed coord compression

void push_lazy(int node) {
	if (st[node].lazy !=0) { //there is shit to lazy set
		st[node].ans = st[node].tr - st[node].tl + 1; // amount set in this interval isj ust size of interval
		int mid = (st[node].tl + st[node].tr) / 2;
		if (st[node].l == -1) { // if no left child, create one (yay)
			st[node].l = cnt++; //create left child
			st[st[node].l].tl = st[node].tl; //left child "border" is same as cur node's border
			st[st[node].l].tr = mid;
		}
		if (st[node].r == -1) { //same shit for right child
			st[node].r = cnt++; //create right child
			st[st[node].r].tl = mid + 1;
			st[st[node].r].tr = st[node].tr;
		}
		st[st[node].l].lazy = st[st[node].r].lazy = 1; //lzset both children
		st[node].lazy = 0;
	}
}

void update(int node, int l, int r) {
	push_lazy(node); //update/create children
	if (l == st[node].tl && r == st[node].tr) { //if we're fully in a node
		st[node].lazy = 1; //set lzset to 1
		push_lazy(node); // no idea why this is here but taking it out breaks the code
		// never mind i figured out why line above is there lmfao
	} else {
		int mid = (st[node].tl + st[node].tr) / 2;
		if (st[node].l == -1) { //same shit again i guess- create children if children weren't there before
			st[node].l = cnt++;
			st[st[node].l].tl = st[node].tl;
			st[st[node].l].tr = mid;
		}
		if (st[node].r == -1) { //same thing; create children
			st[node].r = cnt++;
			st[st[node].r].tl = mid + 1;
			st[st[node].r].tr = st[node].tr;
		}

		if (l > mid) update(st[node].r, l, r); //see where we are, do updates on children depending on where median is
		else if (r <= mid) update(st[node].l, l, r);
		else {
			update(st[node].l, l, mid);
			update(st[node].r, mid + 1, r);
		}

		push_lazy(st[node].l); // no clue why this line or nextl ine is here reeeee
		push_lazy(st[node].r);
		st[node].ans = st[st[node].l].ans + st[st[node].r].ans; // answer is sum of segments, ans stored in st[node].ans
	}
}

int query(int node, int l, int r) {
	push_lazy(node);
	if (l == st[node].tl && r == st[node].tr) return st[node].ans;
	else {
		int mid = (st[node].tl + st[node].tr) / 2; // WHY DO WE DO THE SAME SHIT AS PUSH_LAZY
		if (st[node].l == -1) {
			st[node].l = cnt++;
			st[st[node].l].tl = st[node].tl;
			st[st[node].l].tr = mid;
		}
		if (st[node].r == -1) {
			st[node].r = cnt++;
			st[st[node].r].tl = mid + 1;
			st[st[node].r].tr = st[node].tr;
		}

		if (l > mid) return query(st[node].r, l, r); //see where mid lies wrt l, r and qry accordingly
		else if (r <= mid) return query(st[node].l, l, r);
		else return query(st[node].l, l, mid) + query(st[node].r, mid + 1, r);
	}
}

int32_t main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;

	st[1].ans = 0; st[1].lazy = 0; //yay initialize shit
	st[1].tl = 1; st[1].tr = 1e9;

	int c = 0;
	for(int i=0; i<m; i++) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = query(1, x + c, y + c);
			cout << c << '\n';
		} else update(1, x + c, y + c);
	}
	return 0;
}

• Subtask 1: 0 / 100