oj.uz

답안 #757204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757204 2023-06-12T19:06:49 Z tcmmichaelb139 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 368 ms 108304 KB 
#include "bits/stdc++.h"
using namespace std;

const int SZ = 100'000'001;
struct Node {
	int val;
	int lzAdd;
	Node *c[2];
	Node() {
		val = 0;
		lzAdd = 0;
		c[0] = c[1] = NULL;
	}
	void push(int L, int R) {
		if (lzAdd == 0) return;
		val = R - L + 1;
		if (L != R) {
			if (!c[0]) c[0] = new Node();
			c[0]->lzAdd = lzAdd;
			if (!c[1]) c[1] = new Node();
			c[1]->lzAdd = lzAdd;
		}
		lzAdd = 0;
	}
	void upd(int lo, int hi, int inc, int L = 0, int R = SZ - 1) {
		push(L, R);
		if (lo > R || L > hi) return;
		if (lo <= L && R <= hi) {
			lzAdd = inc;
			push(L, R);
			return;
		}
		int M = (L + R) / 2;
		if (!c[0]) c[0] = new Node();
		c[0]->upd(lo, hi, inc, L, M);
		if (!c[1]) c[1] = new Node();
		c[1]->upd(lo, hi, inc, M + 1, R);
		val = c[0]->val + c[1]->val;
	}
	int query(int lo, int hi, int L = 0, int R = SZ - 1) {
		push(L, R);
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return val;
		int M = (L + R) / 2;
		int res = 0;
		if (c[0]) res += c[0]->query(lo, hi, L, M);
		if (c[1]) res += c[1]->query(lo, hi, M + 1, R);
		return res;
	}
};

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

	int n;
	cin >> n;

	Node seg;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			ans = seg.query(b + ans, c + ans);
			cout << ans << '\n';
		} else {
			seg.upd(b + ans, c + ans, 1);
		}
	}
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 17 ms 5700 KB Output is correct
5 Correct 22 ms 6880 KB Output is correct
6 Correct 21 ms 6584 KB Output is correct
7 Correct 21 ms 6860 KB Output is correct
8 Correct 166 ms 50524 KB Output is correct
9 Correct 303 ms 85872 KB Output is correct
10 Correct 368 ms 96428 KB Output is correct
11 Correct 339 ms 104648 KB Output is correct
12 Correct 364 ms 108304 KB Output is correct
13 Incorrect 68 ms 19512 KB Output isn't correct
14 Halted 0 ms 0 KB -