oj.uz

Submission #50826

# Submission time Handle Problem Language Result Execution time Memory
50826 2018-06-13T15:06:46 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 633 ms 19484 KB 
////////////////////////////////////////////////
//                                            //
//  Author: Muhammad Faishol Amirul Mukminin  //
//                                            //
////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define BTW(x,a,b) a <= x && x <= b

const int MAXE = 4e5+5;

struct child{
	ll sum, minus;
	int pending;
};

int N, Q, K, MAKSI = 0;
int plate[100005];
child segtree[MAXE];
ll ans;

void build_segtree(int ind, int l, int r){
	MAKSI = max(ind, MAKSI);

	if(l == r){
		segtree[ind].sum = plate[l];
		segtree[ind].minus = plate[l]%K;
		segtree[ind].pending = 0;
		return;
	}

	int mid = (l+r)/2;

	build_segtree(2*ind, l, mid);
	build_segtree(2*ind+1, mid+1, r);

	segtree[ind].sum = segtree[2*ind].sum + segtree[2*ind+1].sum;
	segtree[ind].minus = segtree[2*ind].minus + segtree[2*ind+1].minus;
	segtree[ind].pending = 0;
}

void semprotkan(ll &bakteri, int &byk){
	byk --;

	ll kekuatan = 1,
		base = K;

	while(byk > 0 && kekuatan < bakteri){
		if(byk&1) kekuatan = kekuatan*base;

		byk >>= 1;
		base *= base;
	}

	bakteri /= kekuatan;
	byk = 0;
}

void push_pending(int ind, int l, int r){
	if(segtree[ind].pending != 0){
		if(l != r){
			segtree[2*ind].pending += segtree[ind].pending;
			segtree[2*ind+1].pending += segtree[ind].pending;
		}

		segtree[ind].sum = (segtree[ind].sum-segtree[ind].minus)/K;
		segtree[ind].minus = 0;
		semprotkan(segtree[ind].sum, segtree[ind].pending);
	}

}

void update_me(int ind, int l, int r){
	if(l != r){
		push_pending(2*ind, l, (l+r)/2);
		push_pending(2*ind+1, (l+r)/2+1, r);

		segtree[ind].sum = segtree[2*ind].sum + segtree[2*ind+1].sum;
		segtree[ind].minus = segtree[2*ind].minus + segtree[2*ind+1].minus;
	}
}

void query1(int ind, int l, int r, int i_src, ll val){
	push_pending(ind, l, r);

	if(l == r){
		segtree[ind].sum = val;
		segtree[ind].minus = val%K;
		segtree[ind].pending = 0;
		return;
	}

	int mid = (l+r)/2;
	if(i_src <= mid) query1(2*ind, l, mid, i_src, val);
	else query1(2*ind+1, mid+1, r, i_src, val);

	update_me(ind, l, r);
}

void query2(int ind, int l, int r, int l_src, int r_src){
	push_pending(ind, l, r);

	if(l_src <= l && r <= r_src){
		segtree[ind].pending = 1;
		return;
	}

	int mid = (l+r)/2;
	if(l_src <= mid) query2(2*ind, l, mid, l_src, r_src);
	if(mid+1 <= r_src) query2(2*ind+1, mid+1, r, l_src, r_src);

	update_me(ind, l, r);
}

void query3(int ind, int l, int r, int l_src, int r_src){
	push_pending(ind, l, r);

	if(l_src <= l && r <= r_src){
		ans += segtree[ind].sum;
		return;
	}

	int mid = (l+r)/2;
	if(l_src <= mid) query3(2*ind, l, mid, l_src, r_src);
	if(mid+1 <= r_src) query3(2*ind+1, mid+1, r, l_src, r_src);
}

void print_segtree(){
	for(int i=1;i<=2*N+2;i++){
		cout << i << " -> " << segtree[i].sum << " " << segtree[i].minus << " " << segtree[i].pending << endl;
	}
}

int main(){
	cin >> N >> Q >> K;
	for(int i=1;i<=N;i++)
		cin >> plate[i];

	build_segtree(1, 1, N);

	while(Q--){
		int id;
		ll a, b;
		cin >> id >> a >> b;

		if(id == 1){
			query1(1, 1, N, a, b);
		}else if(id == 2){
			query2(1, 1, N, a, b);
		}else{
			ans = 0;
			query3(1, 1, N, a, b);
			cout << ans << endl;
		}

		// cout << "=== " << Q << " ===" << endl;
		// print_segtree();
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 4304 KB Output is correct
2 Correct 363 ms 4304 KB Output is correct
3 Correct 324 ms 7404 KB Output is correct
4 Correct 439 ms 7564 KB Output is correct
5 Correct 554 ms 7680 KB Output is correct
6 Correct 633 ms 7968 KB Output is correct
7 Correct 566 ms 7968 KB Output is correct
8 Correct 501 ms 7968 KB Output is correct
9 Correct 412 ms 7968 KB Output is correct
10 Correct 411 ms 7968 KB Output is correct
11 Correct 422 ms 7968 KB Output is correct
12 Correct 437 ms 7968 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7968 KB Output is correct
2 Correct 74 ms 7968 KB Output is correct
3 Correct 103 ms 7968 KB Output is correct
4 Correct 293 ms 7968 KB Output is correct
5 Correct 335 ms 9968 KB Output is correct
6 Correct 368 ms 11408 KB Output is correct
7 Correct 510 ms 12940 KB Output is correct
8 Correct 339 ms 14248 KB Output is correct
9 Correct 278 ms 15788 KB Output is correct
10 Correct 284 ms 16804 KB Output is correct
11 Correct 322 ms 18392 KB Output is correct
12 Correct 301 ms 19484 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 19484 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -