Submission #887880

#	Time	Username	Problem	Language	Result	Execution time	Memory
887880		NintsiChkhaidze	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	402 ms	208040 KiB

apple

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left t->l,l,(l + r)/2
#define right t->r,(l + r)/2 + 1,r
using namespace std;

const int inf = 1000000000;

struct Node {
    ll s,lz;
    Node *l, *r;
    Node() : s(0), lz(0), l(NULL), r(NULL) { }
};

void children(Node *t){
	if (!(t->l)) t->l = new Node();
	if (!(t->r)) t->r = new Node();
}
void push(Node *t,int l,int r){
	if ((t -> lz) == 0) return;

	int k = t -> lz;
	(t -> l) -> lz = k;
	(t -> l) -> s = (l + r)/2 - l + 1;
	
	(t -> r) -> lz = k;
	(t -> r) -> s = r - (l + r)/2;

	(t -> lz) = 0;
}

void upd(Node *t,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t -> s = (r - l + 1);
		t -> lz = 1;
		return;
	}

	if (!t->l) t->l = new Node();
	if (!t->r) t->r = new Node();

	children(t);
	push(t,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t->s = (t->l)->s + (t->r)->s;
}

int get(Node *t,int l,int r,int L,int R){
	if (t==NULL || r < L || R < l) return 0;
	if (L <= l && r <= R) return t->s;

	children(t);
	push(t,l,r);
	return get(left,L,R) + get(right,L,R);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int q,c = 0;
	cin>>q;

	Node *root = new Node();

	while (q--){
		int tp,l,r;
		cin>>tp>>l>>r;
		l += c;
		r += c;

		if (tp == 1){
			c = get(root,1,inf,l,r);
			cout<<c<<endl;
		}else{
			upd(root,1,inf,l,r);
		}
	}
}

• Subtask 1: 100 / 100