제출 #1327689

#제출 시각아이디문제언어결과실행 시간메모리
1327689baranek_shaun원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
419 ms327680 KiB
#include <bits/stdc++.h>
using namespace std;

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

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

#Verdict Execution timeMemoryGrader output
Fetching results...