Submission #891403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891403	2023-12-22T21:34:47 Z	OAleksa	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	229 ms	141144 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	8 ms	5088 KB	Output is correct
5	Correct	10 ms	5468 KB	Output is correct
6	Correct	10 ms	5468 KB	Output is correct
7	Correct	9 ms	5468 KB	Output is correct
8	Correct	70 ms	32192 KB	Output is correct
9	Correct	153 ms	54128 KB	Output is correct
10	Correct	156 ms	58960 KB	Output is correct
11	Correct	185 ms	65160 KB	Output is correct
12	Correct	163 ms	66020 KB	Output is correct
13	Correct	139 ms	75500 KB	Output is correct
14	Correct	140 ms	75860 KB	Output is correct
15	Correct	216 ms	139116 KB	Output is correct
16	Correct	220 ms	139860 KB	Output is correct
17	Correct	140 ms	81236 KB	Output is correct
18	Correct	138 ms	81240 KB	Output is correct
19	Correct	214 ms	141068 KB	Output is correct
20	Correct	229 ms	141144 KB	Output is correct