제출 #370930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370930		pure_mem	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	1 ms	364 KiB

apple

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 3e5 + 12;
const int INF = 1e9;

struct node{
	node *L, *R;
	int sum = 0, tt = 0;
};

void push(node *v, int tl, int tr){
	if(!v->tt)
		return;
	int tm = (tl + tr) / 2;
	v->L->sum = tm - tl + 1, v->R->sum = tr - tm;
	v->L->tt = v->R->tt = 1, v->tt = 0;
}

void upd(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		v->sum = tr - tl + 1, v->tt = 1;
		return;
	}
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	upd(v->L, tl, tm, l, r);
	upd(v->R, tm + 1, tr, l, r);
	v->sum = v->L->sum + v->R->sum;
}

int get(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return v->sum;
	if(!v->L)
		v->L = new node();
	if(!v->R)
		v->R = new node();
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	return get(v->L, tl, tm, l, r) + get(v->R, tm + 1, tr, l, r);
}

int main () {
//	freopen("f.in", "r", stdin);
//	freopen("f.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	node *root = new node();
	int sums = 0, q;
	cin >> q;
	for(int tc, l, r;q--;){
		cin >> tc >> l >> r, l += sums, r += sums;
		if(tc == 1){
			int ans = get(root, 1, INF, l, r);
			cout << ans << "\n", sums += ans; 
		}
		else{
			upd(root, 1, INF, l, r);
		}
	}
}

• Subtask 1: 0 / 100