oj.uz

답안 #954972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954972 2024-03-29T03:38:24 Z hanifchdn 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 235 ms 128380 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, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};

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

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

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

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
    	int d, x, y;
    	cin >> d >> x >> y;
    	if (d == 1) {
    		c = get(1, 1, 1e9, x + c, y + c);
    		cout << c << "\n";
    	}
    	else {
    		update(1, 1, 1e9, x + c, y + c);
    	}
    }	
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 125428 KB Output is correct
2 Correct 35 ms 125628 KB Output is correct
3 Correct 35 ms 125492 KB Output is correct
4 Correct 44 ms 125468 KB Output is correct
5 Correct 44 ms 125520 KB Output is correct
6 Correct 47 ms 125548 KB Output is correct
7 Correct 43 ms 125556 KB Output is correct
8 Correct 105 ms 126308 KB Output is correct
9 Correct 183 ms 126032 KB Output is correct
10 Correct 178 ms 126032 KB Output is correct
11 Correct 179 ms 126020 KB Output is correct
12 Correct 194 ms 125968 KB Output is correct
13 Correct 165 ms 126140 KB Output is correct
14 Correct 162 ms 125952 KB Output is correct
15 Correct 217 ms 126292 KB Output is correct
16 Correct 212 ms 128340 KB Output is correct
17 Correct 170 ms 128228 KB Output is correct
18 Correct 167 ms 128076 KB Output is correct
19 Correct 222 ms 128116 KB Output is correct
20 Correct 235 ms 128380 KB Output is correct