Submission #954972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954972	2024-03-29T03:38:24 Z	hanifchdn	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	235 ms	128380 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

struct node {
	int sum, lazy, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};

node st[80 * N];
int cnt = 1;

void push(int x, int tl, int tr) {
	if (!st[x].lazy) return;
	st[x].sum = tr - tl + 1;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	st[st[x].l].lazy = st[x].lazy;
	st[st[x].r].lazy = st[x].lazy;
	st[x].lazy = 0;
}

void update(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x, tl, tr);
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	if (r > tm) update(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) update(st[x].l, tl, tm, l, r);
	push(st[x].l, tl, tm);
	push(st[x].r, tm + 1, tr);
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}

int get(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) return st[x].sum;
	int res = 0;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	if (r > tm) res += get(st[x].r, tm + 1, tr, l, r);
	if (l <= tm) res += get(st[x].l, tl, tm, l, r);
	return res;
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, 1, 1e9, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, 1, 1e9, x + c, y + c);
    	}
    }	
}  

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	125428 KB	Output is correct
2	Correct	35 ms	125628 KB	Output is correct
3	Correct	35 ms	125492 KB	Output is correct
4	Correct	44 ms	125468 KB	Output is correct
5	Correct	44 ms	125520 KB	Output is correct
6	Correct	47 ms	125548 KB	Output is correct
7	Correct	43 ms	125556 KB	Output is correct
8	Correct	105 ms	126308 KB	Output is correct
9	Correct	183 ms	126032 KB	Output is correct
10	Correct	178 ms	126032 KB	Output is correct
11	Correct	179 ms	126020 KB	Output is correct
12	Correct	194 ms	125968 KB	Output is correct
13	Correct	165 ms	126140 KB	Output is correct
14	Correct	162 ms	125952 KB	Output is correct
15	Correct	217 ms	126292 KB	Output is correct
16	Correct	212 ms	128340 KB	Output is correct
17	Correct	170 ms	128228 KB	Output is correct
18	Correct	167 ms	128076 KB	Output is correct
19	Correct	222 ms	128116 KB	Output is correct
20	Correct	235 ms	128380 KB	Output is correct