Submission #370933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370933	2021-02-25T05:59:48 Z	pure_mem	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	438 ms	139648 KB

apple

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 3e5 + 12;
const int INF = 1e9;

struct node{
	node *L = nullptr, *R = nullptr;
	int sum = 0, tt = 0;
};

void push(node *v, int tl, int tr){
	if(!v->tt)
		return;
	int tm = (tl + tr) / 2;
	v->L->sum = tm - tl + 1, v->R->sum = tr - tm;
	v->L->tt = v->R->tt = 1, v->tt = 0;
}

void upd(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		v->sum = tr - tl + 1, v->tt = 1;
		return;
	}
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	upd(v->L, tl, tm, l, r);
	upd(v->R, tm + 1, tr, l, r);
	v->sum = v->L->sum + v->R->sum;
}

int get(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return v->sum;
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	return get(v->L, tl, tm, l, r) + get(v->R, tm + 1, tr, l, r);
}

int main () {
//	freopen("f.in", "r", stdin);
//	freopen("f.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	node *root = new node();
	int sums = 0, q;
	cin >> q;
	for(int tc, l, r;q--;){
		cin >> tc >> l >> r, l += sums, r += sums;
		if(tc == 1){
			int ans = get(root, 1, INF, l, r);
			cout << ans << "\n", sums = ans; 
		}
		else{
			upd(root, 1, INF, l, r);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	14 ms	3704 KB	Output is correct
5	Correct	17 ms	4204 KB	Output is correct
6	Correct	21 ms	4076 KB	Output is correct
7	Correct	17 ms	4192 KB	Output is correct
8	Correct	126 ms	30188 KB	Output is correct
9	Correct	276 ms	52564 KB	Output is correct
10	Correct	275 ms	57920 KB	Output is correct
11	Correct	286 ms	62060 KB	Output is correct
12	Correct	287 ms	63980 KB	Output is correct
13	Correct	265 ms	74348 KB	Output is correct
14	Correct	258 ms	75116 KB	Output is correct
15	Correct	412 ms	135684 KB	Output is correct
16	Correct	438 ms	136512 KB	Output is correct
17	Correct	255 ms	77548 KB	Output is correct
18	Correct	262 ms	77548 KB	Output is correct
19	Correct	410 ms	139628 KB	Output is correct
20	Correct	436 ms	139648 KB	Output is correct