Submission #1183318

#TimeUsernameProblemLanguageResultExecution timeMemory
1183318nickolasarapidisMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
468 ms327680 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define F first
#define S second

struct node{
	long val = 0;
	long lazy = 0;
	node *left = nullptr;
	node *right = nullptr;
};

void apply(node *v, long x){
	v->lazy = x;
}

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

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

int main(){
	node *root = new node;
	long M, C = 0;
	cin >> M;
	for(long i = 0; i < M; i++){
		long D, X, Y;
		cin >> D >> X >> Y;
		if(D == 1){
			C = sum(root, 0, 1000000000, X + C, Y + C);
			cout << C << "\n";
		}
		else{
			update(root, 0, 1000000000, X + C, Y + C, 1);
		}
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...