제출 #993899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993899		beaboss	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	356 ms	139348 KiB

apple

#include "bits/stdc++.h"

using namespace std;

const int MX = 1e9 + 10;

#define FOR(i, a, b) for (int i = a; i < b; i++)

struct node {
	int sm, lz;
	node *l, *r;
};
 
node* root;

void down(node *&cur, int l, int m, int r) {
	if (!cur->lz) return;
	if (cur->l == nullptr) cur->l = new node();
	if (cur->r == nullptr) cur-> r = new node();

	cur->l->sm = (m - l);
	cur->r->sm = (r - m);
	cur->l->lz = 1;
	cur->r->lz = 1;

	cur->lz = 0;
}

void up(node *&cur) {
	int res = 0;
	if (cur->l != nullptr) res += cur->l->sm;
	if (cur->r != nullptr) res += cur->r->sm;

	cur->sm = res;
}

void update(int ul, int ur, node *&cur = root, int l = 0, int r = MX) {
		
	
	
	if (ur <= l || ul >= r) return;
	if (cur == nullptr) cur = new node();
	if (ul <= l && ur >= r) {
		// cout << l << r << endl;
		cur->sm = r-l;
		cur->lz = 1;
		// cout << l << r <<
		return;
	}

	
	down(cur, l, (l + r) / 2, r);

	int m = (l + r) / 2;
	update(ul, ur, cur->l, l, m);
	update(ul, ur, cur->r, m, r);

	up(cur);
}

int query(int ql, int qr, node *&cur = root, int l = 0, int r = MX) {

	if (qr <= l || ql >= r) return 0;
	if (cur == nullptr) return 0;
	if (ql <= l && qr >= r) {
		// cout << l << ' ' << r << ' ' << cur->sm << endl;

		return cur->sm;
	}

	
	
	down(cur, l, (l + r) / 2, r);

	int m = (l + r) / 2;
	return query(ql, qr, cur->l, l, m) + query(ql, qr, cur->r, m, r);
}


int main() {
	ios::sync_with_stdio(false);cin.tie(nullptr);

	int n;
	cin >> n;
	int c = 0;
	FOR(i, 0, n) {
		int t, x, y;
		cin >> t >> x >> y;

		if (t == 1) {
			c = query(x + c, y + 1 + c);
			cout << c << endl;
		} else {
			update(x + c, y + 1 + c);
		}
	}

}

• Subtask 1: 100 / 100