Submission #891403

#	Time	Username	Problem	Language	Result	Execution time	Memory
891403		OAleksa	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	229 ms	141144 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 1e7;
const int inf = 1e9 + 69;
int lc[N], rc[N], lzy[N], st[N], node, c, q;
void push(int v, int tl, int tr) {
	int mid = (tl + tr) / 2;
	if (lzy[v]) {
		st[rc[v]] = tr - mid;
		lzy[rc[v]] = tr - mid;
		st[lc[v]] = mid - tl + 1;
		lzy[lc[v]] = mid - tl + 1;
		lzy[v] = 0;
	}
}
void upd(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		lzy[v] = tr - tl + 1;
		st[v] =  tr - tl + 1;
	}
	else {
		int mid = (tl + tr) / 2;
		if(lc[v] == 0) 
			lc[v] = ++node;
		if (rc[v] == 0)
			rc[v] = ++node;
		push(v, tl, tr);
		upd(lc[v], tl, mid, l, r);
		upd(rc[v], mid + 1, tr, l, r);
		st[v] = st[lc[v]] + st[rc[v]];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		if(lc[v] == 0) 
			lc[v] = ++node;
		if (rc[v] == 0)
			rc[v] = ++node;
		push(v, tl, tr);
		return get(lc[v], tl, mid, l, r) + get(rc[v], mid + 1, tr, l, r);
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
  cout.tie(nullptr); 
  cin.tie(nullptr);
  //freopen("newbarn.in", "r", stdin);
  //freopen(newbarn.out", "w", stdout);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> q;
  	while (q--) {
  		int t, l, r;
  		cin >> t >> l >> r;
  		l += c, r += c;
  		if (t == 2) 
  			upd(0, 1, inf, l, r);
  		else {
  			c = get(0, 1, inf, l, r);
  			cout << c << '\n';
  		}
  	}
  }
  return 0;
}

• Subtask 1: 100 / 100