제출 #954975

#제출 시각아이디문제언어결과실행 시간메모리
954975hanifchdnMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
214 ms127448 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
 
const int N = 1e5 + 5;
 
struct node {
	int sum, lazy, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};
 
node st[80 * N];
int cnt = 1;
 
void push(int x, int tl, int tr) {
	if (!st[x].lazy) return;
	st[x].sum = tr - tl + 1;
	if (tl == tr) {
		st[x].lazy = 0;
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	st[st[x].l].lazy = st[x].lazy;
	st[st[x].r].lazy = st[x].lazy;
	st[x].lazy = 0;
}
 
void update(int x, int tl, int tr, int l, int r) {
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (tr < l or r < tl) return;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x, tl, tr);
		return;
	}
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	update(st[x].l, tl, tm, l, r);
	update(st[x].r, tm + 1, tr, l, r);
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}
 
int get(int x, int tl, int tr, int l, int r) {
	if (tr < l or r < tl) return 0;
	push(x, tl, tr);
	int tm = (tl + tr) / 2;
	if (l <= tl and tr <= r) return st[x].sum;
	if (st[x].l == -1) {
		st[x].l = ++cnt;
		st[x].r = ++cnt;
	}
	return get(st[x].l, tl, tm, l, r) + get(st[x].r, tm + 1, tr, l, r);
}
 
int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, 1, 1e9, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, 1, 1e9, x + c, y + c);
    	}
    }	
}  
#Verdict Execution timeMemoryGrader output
Fetching results...