oj.uz

Submission #50827

# Submission time Handle Problem Language Result Execution time Memory
50827 2018-06-13T15:08:53 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 772 ms 7888 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;

		if(base > bakteri){
			kekuatan = bakteri+1;
			break;
		}
	}

	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 Incorrect 11 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 4196 KB Output is correct
2 Correct 401 ms 4196 KB Output is correct
3 Correct 416 ms 7196 KB Output is correct
4 Correct 465 ms 7436 KB Output is correct
5 Correct 522 ms 7548 KB Output is correct
6 Correct 772 ms 7692 KB Output is correct
7 Correct 613 ms 7748 KB Output is correct
8 Correct 734 ms 7748 KB Output is correct
9 Correct 528 ms 7748 KB Output is correct
10 Correct 439 ms 7748 KB Output is correct
11 Correct 502 ms 7888 KB Output is correct
12 Correct 489 ms 7888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 7888 KB Output is correct
2 Correct 66 ms 7888 KB Output is correct
3 Correct 154 ms 7888 KB Output is correct
4 Correct 379 ms 7888 KB Output is correct
5 Correct 460 ms 7888 KB Output is correct
6 Correct 511 ms 7888 KB Output is correct
7 Correct 557 ms 7888 KB Output is correct
8 Correct 511 ms 7888 KB Output is correct
9 Correct 364 ms 7888 KB Output is correct
10 Correct 341 ms 7888 KB Output is correct
11 Correct 359 ms 7888 KB Output is correct
12 Correct 353 ms 7888 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 7888 KB Output isn't correct
2 Halted 0 ms 0 KB -