Submission #1264900

#TimeUsernameProblemLanguageResultExecution timeMemory
1264900nickolasarapidisMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
541 ms254560 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define F first
#define S second
#define pb push_back
 
const long MAXN = 200000;

struct node{
	int sum, lazy;
	node *left, *right;
	
	node(int v = 0, int l = 0) : sum(v), lazy(l), left(nullptr), right(nullptr) {}
};

void apply(node*& v){
	if(!v) v = new node();
	v->lazy = 1;
}

void update(node*& v, int l, int r, int a, int b){
	if(!v) v = new node();
	if(v->lazy == 1){
		v->sum = r - l + 1;
		if(l != r){
			apply(v->left);
			apply(v->right);
		}
		v->lazy = 0;
	}
	if(l > b or r < a) return;
	if(l >= a and r <= b){
		v->sum = r - l + 1;
		if(l != r){
			apply(v->left);
			apply(v->right);
		}
		return;
	}
	int m = (l + r)/2;
	update(v->left, l, m, a, b);
	update(v->right, m + 1, r, a, b);
	v->sum = v->left->sum + v->right->sum;
	return;
}

int query(node*& v, int l, int r, int a, int b){
	if(!v) v = new node();
	if(v->lazy == 1){
		v->sum = r - l + 1;
		if(l != r){
			apply(v->left);
			apply(v->right);
		}
		v->lazy = 0;
	}
	if(l > b or r < a) return 0;
	if(l >= a and r <= b) return v->sum;
	int m = (l + r)/2;
	return query(v->left, l, m, a, b) + query(v->right, m + 1, r, a, b);
}
 
int main(){
	int M, C = 0;
	cin >> M;
	node *root = new node();
	for(int i = 0; i < M; i++){
		int d, l, r;
		cin >> d >> l >> r;
		if(d == 1){
			C = query(root, 0, 1e9 - 1, l + C, r + C);
			cout << C << "\n";
		}
		else{
			update(root, 0, 1e9 - 1, l + C, r + C);
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...