oj.uz

답안 #791307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791307 2023-07-24T01:02:13 Z lukehsiao 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 318 ms 139508 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
	int sum;
	bool lz;
	node* c[2];
	node() {
		sum = 0;
		lz = false;
		c[0] = c[1] = NULL;
	}
	void push(int l, int mid, int r) {
		if (lz) {
			c[0]->sum = mid-l+1;
			c[1]->sum = r-mid;
			c[0]->lz = c[1]->lz = true;
			lz = false;
		}
	}
	void upd(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			sum = r-l+1;
			lz = true;
		} else {
			int mid = (l+r)/2;
			if (!c[0]) c[0] = new node();
			if (!c[1]) c[1] = new node();
			push(l, mid, r);
			c[0]->upd(a, b, l, mid);
			c[1]->upd(a, b, mid+1, r);
			sum = c[0]->sum + c[1]->sum;
		}
	}
	int qry(int a, int b, int l=0, int r=1e9-1) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return sum;
		int mid = (l+r)/2;
		if (!c[0]) c[0] = new node();
		if (!c[1]) c[1] = new node();
		push(l, mid, r);
		return c[0]->qry(a, b, l, mid) + c[1]->qry(a, b, mid+1, r);
	}
};

int m, c;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	node root = node();

	cin >> m;
	for (int i=0, d, x, y; i<m; ++i) {
		cin >> d >> x >> y;
		if (d == 1) {
			c = root.qry(x+c-1, y+c-1);
			cout << c << '\n';
		} else {
			root.upd(x+c-1, y+c-1);
		}
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 8 ms 3428 KB Output is correct
5 Correct 11 ms 4172 KB Output is correct
6 Correct 10 ms 4052 KB Output is correct
7 Correct 11 ms 4180 KB Output is correct
8 Correct 78 ms 30140 KB Output is correct
9 Correct 168 ms 52320 KB Output is correct
10 Correct 172 ms 57772 KB Output is correct
11 Correct 192 ms 61956 KB Output is correct
12 Correct 190 ms 63832 KB Output is correct
13 Correct 167 ms 74180 KB Output is correct
14 Correct 179 ms 74972 KB Output is correct
15 Correct 289 ms 135476 KB Output is correct
16 Correct 318 ms 136440 KB Output is correct
17 Correct 174 ms 77516 KB Output is correct
18 Correct 169 ms 77456 KB Output is correct
19 Correct 279 ms 139420 KB Output is correct
20 Correct 282 ms 139508 KB Output is correct