oj.uz

답안 #502056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502056 2022-01-05T07:24:01 Z desmond_willow Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 4546 ms 3980 KB 
#include<bits/stdc++.h>

using namespace std;

int n, q, k;

void build (int l, int r, long long int* segtree, int pos) {
	if (l == r) {
		//takes input in the order 1...n
		cin >> segtree[pos];
		return;
	}
	int mid = (l + r)/2;
	build (l, mid, segtree, pos * 2);
	build (mid + 1, r, segtree, pos * 2 + 1);
	segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}

int query (int l, int r, int target_l, int target_r, long long int* segtree, int pos) {
	// no intersection
	if (r < target_l || l > target_r) {
		return 0;
	} if (target_l <= l && r <= target_r) { //total intersection
		#ifdef DEBUG
		printf ("Total intersection querying range (%d, %d): %lld\n", l, r, segtree[pos]);
		#endif
		return segtree[pos];
	} else { //partial intersection
		int mid = (l + r)/2;
		return query(l, mid, target_l, target_r, segtree, pos*2) + 
			query(mid + 1, r, target_l, target_r, segtree, pos*2 + 1);
	}
}

void spray (int l, int r, int target_l, int target_r, long long int* segtree, int pos) {
	// no intersection
	if (r < target_l || l > target_r) {return;}

	if (target_l <= l && r <= target_r && l == r) {
		#ifdef DEBUG
		printf ("Sprayed %dth dish: was %lld, now is %lld\n", l, segtree[pos], segtree[pos] / k);
		#endif

		segtree[pos] = segtree[pos] / k;
		return;
	}

	//micro-optimization: don't need to visit further subnodes, mark whole subtree as zero and move on
	if (target_l <= l && r <= target_r && segtree[pos] < k) {
		segtree[pos] = 0;
		return;
	}

	int mid = (l + r)/2;
	spray (l, mid, target_l, target_r, segtree, pos * 2);
	spray (mid + 1, r, target_l, target_r, segtree, pos * 2 + 1);

	#ifdef DEBUG
	printf ("Updating range (%d, %d) to %lld (from %lld)\n", l, r, segtree[pos * 2] + segtree[pos * 2 + 1], segtree[pos]);
	#endif

	segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}

void update (int l, int r, long long int* segtree, int pos, int index, int value) {
	if (l == r) {
		segtree[pos] = value;
		return;
	}
	
	int mid = (l + r)/2;
	if (index <= mid) {
		update (l, mid, segtree, pos * 2, index, value);
	} else {
		update (mid + 1, r, segtree, pos * 2 + 1, index, value);
	}
	segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
}

#ifdef DEBUG
void view_arr (int l, int r, long long int* segtree, int pos) {
	if (l == r) {
		printf ("%02lld ", segtree[pos]);
		return;
	}
	int mid = (l + r)/2;
	view_arr (l, mid, segtree, pos * 2);
	view_arr (mid + 1, r, segtree, pos * 2 + 1);
}
#endif

// we can't use a range-update range-query segtree as is because
// integer division is not distributive
// i.e. 2//3 + 1//3 != 3//3
// thus we can't apply division to sum of dishes directly
// we'll have to update all dishes individually
int main () {
	cin >> n >> q >> k;
	long long int segtree[4*n + 1];
	build (1, n, segtree, 1);

	for (int i = 0; i < q; i++) {
		int op_type; cin >> op_type;
		if (op_type == 1) {
			int ind, val; cin >> ind >> val;
			#ifdef DEBUG
			printf ("Setting %d dish to %d\n", ind, val);
			#endif
			update (1, n, segtree, 1, ind, val);
		} else if (op_type == 2) {
			int l, r; cin >> l >> r;
			#ifdef DEBUG
			printf ("Spraying %d to %d dishes\n", l, r);
			#endif
			spray (1, n, l, r, segtree, 1);
		} else if (op_type == 3) {
			int l, r; cin >> l >> r;
			#ifdef DEBUG
			printf ("Querying amount in %d to %d dishes\n", l, r);
			#endif
			cout << query(1, n, l, r, segtree, 1) << endl;
		}
		#ifdef DEBUG
		view_arr (1, n, segtree, 1);
		cout << endl;
		#endif
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4546 ms 3980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 3524 KB Output isn't correct
2 Halted 0 ms 0 KB -