답안 #954969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954969 2024-03-29T02:51:02 Z hanifchdn 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
247 ms 240208 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[50 * 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 Correct 61 ms 117840 KB Output is correct
2 Correct 26 ms 117840 KB Output is correct
3 Correct 23 ms 117848 KB Output is correct
4 Correct 31 ms 117840 KB Output is correct
5 Correct 38 ms 117852 KB Output is correct
6 Correct 34 ms 117848 KB Output is correct
7 Correct 35 ms 117852 KB Output is correct
8 Correct 98 ms 118868 KB Output is correct
9 Correct 201 ms 119852 KB Output is correct
10 Correct 199 ms 119792 KB Output is correct
11 Correct 209 ms 119832 KB Output is correct
12 Correct 209 ms 119964 KB Output is correct
13 Correct 199 ms 120404 KB Output is correct
14 Correct 174 ms 120232 KB Output is correct
15 Runtime error 247 ms 240208 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -