Submission #668765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668765	2022-12-04T23:41:59 Z	thiago_bastos	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	336 ms	139648 KB

apple

#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

struct No {
	int cnt;
	bool lazy;
	No *left, *right;
	No() {
		cnt = 0;
		lazy = false;
		left = right = nullptr;
	}
} *r {};

void push(No **p, int n) {
	if(!*p || !(*p)->lazy) return;
	if(!(*p)->left) (*p)->left = new No;
	if(!(*p)->right) (*p)->right = new No;
	No* left = (*p)->left, *right = (*p)->right;
	left->lazy = right->lazy = true;
	left->cnt = (n + 1) / 2;
	right->cnt = n / 2;
	(*p)->lazy = false;
}

void upd(int l, int r, int lo, int hi, No **p) {
	if(l > r || lo > hi || r < lo || l > hi) return;
	else if(lo >= l && hi <= r) {
		if(!*p) *p = new No;
		(*p)->lazy = true;
		(*p)->cnt = hi - lo + 1;
		return;
	}
	int m = (lo + hi) / 2;
	push(p, hi - lo + 1);
	if(!*p) *p = new No;
	upd(l, r, lo, m, &(*p)->left);
	upd(l, r, m + 1, hi, &(*p)->right);
	No *left = (*p)->left, *right = (*p)->right;
	if(left && right) (*p)->cnt = left->cnt + right->cnt;
	else (*p)->cnt = left ? left->cnt : right->cnt;
}

int query(int l, int r, int lo, int hi, No **p) {
	if(l > r || lo > hi || r < lo || l > hi || !*p) return 0;
	else if(lo >= l && hi <= r) return (*p)->cnt;
	int m = (lo + hi) / 2;
	push(p, hi - lo + 1);
	int v1 = query(l, r, lo, m, &(*p)->left);
	int v2 = query(l, r, m + 1, hi, &(*p)->right);
	return v1 + v2;
}

void solve() {
	int c = 0, q;

	cin >> q;

	while(q--) {
		int t, x, y;
		cin >> t >> x >> y;
		x += c, y += c;
		if(t == 1) {
			int ans = query(x, y, 1, INF, &r);
			cout << ans << '\n';
			c = ans;
		} else upd(x, y, 1, INF, &r);
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	296 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	11 ms	3424 KB	Output is correct
5	Correct	14 ms	4160 KB	Output is correct
6	Correct	16 ms	4052 KB	Output is correct
7	Correct	14 ms	4104 KB	Output is correct
8	Correct	111 ms	30144 KB	Output is correct
9	Correct	218 ms	52296 KB	Output is correct
10	Correct	225 ms	57800 KB	Output is correct
11	Correct	229 ms	61912 KB	Output is correct
12	Correct	228 ms	63836 KB	Output is correct
13	Correct	215 ms	74216 KB	Output is correct
14	Correct	205 ms	74956 KB	Output is correct
15	Correct	333 ms	135412 KB	Output is correct
16	Correct	323 ms	136432 KB	Output is correct
17	Correct	208 ms	77516 KB	Output is correct
18	Correct	220 ms	77596 KB	Output is correct
19	Correct	336 ms	139424 KB	Output is correct
20	Correct	332 ms	139648 KB	Output is correct