Submission #96067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96067	2019-02-05T15:41:32 Z	Shafin666	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	806 ms	251236 KB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define to second
#define cost first
typedef long long ll;
typedef long double ld;
using namespace std;
 
struct Node {
	ll sum, lazy;
	Node *l, *r;
	Node() : sum(0), lazy(0), l(NULL), r(NULL) { }
}; Node *root;
 
void propagate(Node *v, ll len) {
	if(v->lazy) {
		if(v->l == NULL) v->l = new Node;
		v->l->sum = len/2;
		v->l->lazy = 1;
 
		if(v->r == NULL) v->r = new Node;
		v->r->sum = len/2;
		v->r->lazy = 1;
 
		v->sum = len;
		v->lazy = 0;
	}
}
 
void add(Node *v, ll L, ll R, ll l, ll r) {
	if(L >= l && R <= r) { 
		v->sum =  (R-L+1); 
		v->lazy = 1;
		return; 
	}
	propagate(v, R-L+1);
 
	ll mid = (L+R)/2;
 
	if(l <= mid) {
		if(v->l == NULL) v->l = new Node;
		add(v->l, L, mid, l, min(r, mid));
	}
	if(mid < r) {
		if(v->r == NULL) v->r = new Node;
		add(v->r, mid+1, R, max(l, mid+1), r);
	}
 
	v->sum = 0;
	if(v->l != NULL) v->sum += v->l->sum;
	if(v->r != NULL) v->sum += v->r->sum;
}
 
ll get(Node *v, ll L, ll R, ll l, ll r) {
	if(v == NULL) return 0;
 
	ll mid = (L+R)/2;
	ll ans = 0;
 
	propagate(v, R-L+1);
	if(L >= l && R <= r) return v->sum;
	if(l <= mid) ans += get(v->l, L, mid, l, min(mid, r));
	if(mid < r) ans += get(v->r, mid+1, R, max(mid+1, l), r);
 
	return ans;
}
 
void update(ll x, ll y) { add(root, 1, (1<<30), x, y); }
ll query(ll x, ll y) { return get(root, 1, (1<<30), x, y); }
 
int main()
{
	ll n, c = 0;
	ll x, l, r;
 
	root = new Node;
 
	cin >> n;
	while(n--) {
		cin >> x >> l >> r;
 
		if(x == 2) update(l+c, r+c);
		else {
			ll ans = query(l+c, r+c);
			c = ans;
			cout << ans << endl;
		}
	}
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	29 ms	5880 KB	Output is correct
5	Correct	36 ms	7032 KB	Output is correct
6	Correct	36 ms	6776 KB	Output is correct
7	Correct	36 ms	7032 KB	Output is correct
8	Correct	259 ms	52724 KB	Output is correct
9	Correct	588 ms	95108 KB	Output is correct
10	Correct	484 ms	100736 KB	Output is correct
11	Correct	587 ms	108408 KB	Output is correct
12	Correct	545 ms	111596 KB	Output is correct
13	Correct	516 ms	132268 KB	Output is correct
14	Correct	510 ms	133112 KB	Output is correct
15	Correct	806 ms	243276 KB	Output is correct
16	Correct	806 ms	245276 KB	Output is correct
17	Correct	507 ms	137692 KB	Output is correct
18	Correct	497 ms	137592 KB	Output is correct
19	Correct	748 ms	251104 KB	Output is correct
20	Correct	731 ms	251236 KB	Output is correct