Submission #1327666

#TimeUsernameProblemLanguageResultExecution timeMemory
1327666baranek_shaunMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
322 ms267424 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Vertex{
	int L, R, sum, lazy, len;
	Vertex *left, *right;
	
	Vertex(int l, int r, int s, int laz, int length) :
		L(l), R(r), sum(s), lazy(laz), len(length) {};
};

struct Dynamic_Segment_Tree{
	void extend(Vertex *&w){
		int l = w->L; int r = w->R; int m = (l + r)/2;
		if(l == r) return;
		if(w->left == nullptr) w->left = new Vertex(l, m, 0, w->lazy, w->len/2);
		if(w->right == nullptr) w->right = new Vertex(m+1, r, 0, w->lazy, w->len/2);
	}
	
	void push(Vertex *&w){
		if(w->len == 1 || w->lazy == -1){
			return;
		}
		w->left->sum = w->left->len*w->lazy;
		w->left->lazy = w->lazy;
		w->right->sum = w->right->len*w->lazy;
		w->right->lazy = w->lazy;
		w->lazy = -1;
	}
	
	void range_set(Vertex *w, int L, int R, int l, int r, int len, int v){
		extend(w); push(w);
		if(l > R || r < L){
			return;
		}
		if(l >= L && r <= R){
			w->sum = len*v;
			w->lazy = v;
			return;
		}
		int m = (l + r)/2;
		range_set(w->left, L, R, l, m, len/2, v);
		range_set(w->right, L, R, m+1, r, len/2, v);
		w->sum = w->left->sum + w->right->sum;
	}
	
	int range_sum(Vertex *w, int L, int R, int l, int r){
		extend(w); push(w);
		if(l > R || r < L){
			return 0;
		}
		if(l >= L && r <= R){
			return w->sum;
		}
		int m = (l + r)/2;
		return range_sum(w->left, L, R, l, m) + range_sum(w->right, L, R, m+1, r);
	}
	
};


int base = (1 << 30);
Dynamic_Segment_Tree tree;
Vertex *root = new Vertex(0, base-1, 0, -1, base);
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int Q, C = 0;
	cin >> Q;
	while(Q--){
		int type, x, y;
		cin >> type >> x >> y;
		if(type == 1){
			C = tree.range_sum(root, x+C-1, y+C-1, 0, base-1);
			cout << C << '\n';
		}
		else{
			tree.range_set(root, x+C-1, y+C-1, 0, base-1, base, 1);
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...