답안 #954517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954517 2024-03-28T05:44:47 Z hanifchdn 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
83 ms 262144 KB
#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, tl, tr, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};

node st[200 * N];
int cnt = 1;

void push(int x) {
	if (!st[x].lazy) return;
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	st[x].sum = st[x].tr - st[x].tl + 1;
	if (st[x].l == -1 and tl != tr) {
		st[x].l = ++cnt;
		st[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	if (tl != tr) {
		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 l, int r) {
	push(x);
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	if (tr < l or r < tl) return;
	if (l <= tl and tr <= r) {
		st[x].lazy = 1;
		push(x);
		return;
	}
	if (st[x].l == -1 and tl != tr) {
		st[x].l = ++cnt;
		st[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	if (tl != tr) {
		update(st[x].l, l, r);
		update(st[x].r, l, r);
	}
	st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
}

int get(int x, int l, int r) {
	push(x);
	int tl = st[x].tl, tr = st[x].tr, tm = (tl + tr) / 2;
	if (tr < l or r < tl) return 0;
	if (l <= tl and tr <= r) return st[x].sum;
	if (st[x].l == -1 and tl != tr) {
		st[x].l = ++cnt;
		st[cnt].tl = tl;
		st[cnt].tr = tm;
		st[x].r = ++cnt;
		st[cnt].tl = tm + 1;
		st[cnt].tr = tr;
	}
	return get(st[x].l, l, r) + get(st[x].r, l, r);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    st[1].sum = 0;
    st[1].lazy = 0;
    st[1].tl = 1;
    st[1].tr = 1e9;
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, x + c, y + c);
    	}
    }	
}  
# 결과 실행 시간 메모리 Grader output
1 Runtime error 83 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -