제출 #1304439

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

// #define int long long

struct node {
	int left = -1;
	int right = -1;
	int sum = 0;
	int lazy = 0;
};

int cur;
vector<node> tree;

void apply(int v, int len, int val){
	if (val == 1){
		tree[v].lazy = val;
		tree[v].sum = len * val;
	}
}

int merge(int a, int b){
	return (a + b);
}

void push(int v, int s, int e){
	int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2;
	if (lc == -1){
		tree[v].left = ++cur;
		tree.push_back(node());
	}
	if (rc == -1){
		tree[v].right = ++cur;
		tree.push_back(node());
	}
	
	apply(tree[v].left, mid - s, tree[v].lazy);
	apply(tree[v].right, e - mid, tree[v].lazy);
	tree[v].lazy = 0;
}

void upd(int val, int l, int r, int v = 0, int s = 0, int e = 1e9 + 5){
	if (e <= l or r <= s) return;
	if (l <= s && e <= r){
		apply(v, e - s, val);
		return;
	}
	push(v, s, e);
	int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2;
	
	upd(val, l, r, lc, s, mid);
	upd(val, l, r, rc, mid, e);
	
	tree[v].sum = merge(tree[lc].sum, tree[rc].sum);
}

int sum(int l, int r, int v = 0, int s = 0, int e = 1e9 + 5){
	if (e <= l or r <= s) return 0;
	if (l <= s && e <= r) return tree[v].sum;
	push(v, s, e);
	int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2;
	return merge(sum(l, r, lc, s, mid), sum(l, r, rc, mid, e));
}


signed main(){
	int m; cin >> m;
	tree.push_back(node());
	
	int c = 0;
	
	for (int i = 1; i <= m; i++){
		int t; cin >> t;
		int l, r; cin >> l >> r;
		r++;
		l += c, r += c;
		if (t == 1){
			c = sum(l, r);
			cout << c << endl; 		
		}
		else {
			upd(1, l, r);
		}
	}
	
	return 0;	
}
#Verdict Execution timeMemoryGrader output
Fetching results...