Submission #853327

#	Time	Username	Problem	Language	Result	Execution time	Memory
853327		serifefedartar	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	244 ms	214404 KiB

apple

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;

struct Node {
	int l, r, sum;
	bool lazy;
	int left, right;
	Node(int a, int b) : l(a), r(b), sum(0), lazy(0), left(-1), right(-1) { }
	Node() : l(-1), r(-1), sum(0), lazy(0), left(-1), right(-1) { }
};
Node sg[90*MAXN];
int no = 2;

void add(int x) {
	if (sg[x].left == -1 && sg[x].l != sg[x].r) {
		int mid = (sg[x].l + sg[x].r) / 2;
		sg[x].left = no;
		sg[x].right = no+1;
		sg[no++] = Node(sg[x].l, mid);
		sg[no++] = Node(mid+1, sg[x].r);
	}
}

void push(int x) {
	if (sg[x].lazy) {
		sg[x].sum = sg[x].r - sg[x].l + 1;
		if (sg[x].l != sg[x].r) {
			add(x);
			sg[sg[x].left].lazy = 1;
			sg[sg[x].left].sum = sg[sg[x].left].r - sg[sg[x].left].l + 1;
			sg[sg[x].right].lazy = 1;
			sg[sg[x].right].sum = sg[sg[x].right].r - sg[sg[x].right].l + 1;
		}
		sg[x].lazy = 0;
	}
}

void update(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return ;
	if (a <= sg[x].l && sg[x].r <= b) {
		sg[x].lazy = 1;
		push(x);
		return ;
	}
	add(x);
	push(x);
	update(sg[x].left, a, b);
	update(sg[x].right, a, b);
	sg[x].sum = sg[sg[x].left].sum + sg[sg[x].right].sum; 
}

int query(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return 0;
	push(x);
	if (a <= sg[x].l && sg[x].r <= b)
		return sg[x].sum;
	add(x);
	return query(sg[x].left, a, b) + query(sg[x].right, a, b);
}

int M, D, X, Y, C = 0;
int main() {
	fast
	cin >> M;

	sg[1] = Node(1, 1e9); 
	while (M--) {
		cin >> D >> X >> Y;
		if (D == 1) {
			C = query(1, X + C, Y + C);
			cout << C << "\n";
		} else
			update(1, X + C, Y + C);
	}
}

• Subtask 1: 100 / 100