oj.uz

Submission #50828

# Submission time Handle Problem Language Result Execution time Memory
50828 2018-06-13T15:09:51 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 660 ms 7792 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(base > bakteri){
			kekuatan = bakteri+1;
			break;
		}
		
		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 Incorrect 8 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 506 ms 4196 KB Output is correct
2 Correct 414 ms 4196 KB Output is correct
3 Correct 365 ms 7428 KB Output is correct
4 Correct 489 ms 7548 KB Output is correct
5 Correct 606 ms 7644 KB Output is correct
6 Correct 660 ms 7792 KB Output is correct
7 Correct 561 ms 7792 KB Output is correct
8 Correct 593 ms 7792 KB Output is correct
9 Correct 398 ms 7792 KB Output is correct
10 Correct 454 ms 7792 KB Output is correct
11 Correct 423 ms 7792 KB Output is correct
12 Correct 432 ms 7792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7792 KB Output is correct
2 Correct 62 ms 7792 KB Output is correct
3 Correct 79 ms 7792 KB Output is correct
4 Correct 297 ms 7792 KB Output is correct
5 Correct 487 ms 7792 KB Output is correct
6 Correct 475 ms 7792 KB Output is correct
7 Correct 555 ms 7792 KB Output is correct
8 Correct 478 ms 7792 KB Output is correct
9 Correct 357 ms 7792 KB Output is correct
10 Correct 336 ms 7792 KB Output is correct
11 Correct 300 ms 7792 KB Output is correct
12 Correct 315 ms 7792 KB Output is correct

Subtask #4
0 / 75.0

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