Submission #887297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
887297	2023-12-14T08:44:21 Z	alex_2008	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	283 ms	73908 KB

apple

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <bitset>
typedef long long ll;
using namespace std;
const int N = 1e7 + 10;
int sz = 1;
int lazy[N];
int sm[N];
int l[N];
int r[N];
void update(int v, int tl, int tr, int ql, int qr) {
	if (tl > qr || tr < ql) {
		return;
	}
	if (tl >= ql && tr <= qr) {
		sm[v] = (tr - tl + 1);
		lazy[v] = 1;
		return;
	}
	if (!l[v]) l[v] = ++sz;
	if (!r[v]) r[v] = ++sz;
	int tm = (tl + tr) / 2;
	if (lazy[v]) {
		lazy[l[v]] = 1;
		sm[l[v]] = (tm - tl + 1);
		lazy[r[v]] = 1;
		sm[r[v]] = (tr - tm);
		lazy[v] = 0;
	}
	update(l[v], tl, tm, ql, qr);
	update(r[v], tm + 1, tr, ql, qr);
	sm[v] = sm[l[v]] + sm[r[v]];
}
int sum(int v, int tl, int tr, int ql, int qr) {
	if (tr < ql || tl > qr) return 0;
	if (tl >= ql && tr <= qr) {
		return sm[v];
	}
	if (!l[v]) l[v] = ++sz;
	if (!r[v]) r[v] = ++sz;
	int tm = (tl + tr) / 2;
	if (lazy[v]) {
		lazy[l[v]] = 1;
		sm[l[v]] = (tm - tl + 1);
		lazy[r[v]] = 1;
		sm[r[v]] = (tr - tm);
		lazy[v] = 0;
	}
	return sum(l[v], tl, tm, ql, qr) + sum(r[v], tm + 1, tr, ql, qr);
}
int main() {
	int m, c = 0;
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 2) {
			update(1, 1, 1e9, x + c, y + c);
		}
		else {
			c = sum(1, 1, 1e9, x + c, y + c);
			cout << c << "\n";
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	15 ms	1880 KB	Output is correct
5	Correct	19 ms	3924 KB	Output is correct
6	Correct	18 ms	3928 KB	Output is correct
7	Correct	18 ms	3932 KB	Output is correct
8	Correct	102 ms	16460 KB	Output is correct
9	Correct	211 ms	31056 KB	Output is correct
10	Correct	260 ms	32412 KB	Output is correct
11	Correct	238 ms	33360 KB	Output is correct
12	Correct	238 ms	34144 KB	Output is correct
13	Correct	215 ms	40784 KB	Output is correct
14	Correct	219 ms	41212 KB	Output is correct
15	Correct	268 ms	72528 KB	Output is correct
16	Correct	275 ms	72944 KB	Output is correct
17	Correct	237 ms	41928 KB	Output is correct
18	Correct	210 ms	41808 KB	Output is correct
19	Correct	283 ms	73728 KB	Output is correct
20	Correct	279 ms	73908 KB	Output is correct