oj.uz

Submission #50773

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

typedef long long ll;

const int MAXE = 4e5+5;

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

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

void build_segtree(int ind, int l, int r){
	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 push_pending(int ind){
	segtree[ind].pending = 0;
	segtree[ind].sum = (segtree[ind].sum-segtree[ind].minus)/K;
	segtree[ind].minus = 0;

	if(segtree[2*ind].pending == 1 && 2*ind < MAXE) push_pending(2*ind);
	if(segtree[2*ind+1].pending == 1 && 2*ind+1 < MAXE) push_pending(2*ind+1);

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

void update_me(int ind){
	segtree[ind].sum = 0;
	segtree[ind].minus = 0;
	segtree[ind].pending = 0;

	if(segtree[2*ind].pending == 1){
		segtree[ind].sum += (segtree[2*ind].sum-segtree[2*ind].minus)/K;
	}else{
		segtree[ind].sum += segtree[2*ind].sum;
		segtree[ind].minus += segtree[2*ind].minus;
	}

	if(segtree[2*ind+1].pending == 1){
		segtree[ind].sum += (segtree[2*ind+1].sum-segtree[2*ind+1].minus)/K;
	}else{
		segtree[ind].sum += segtree[2*ind+1].sum;
		segtree[ind].minus += segtree[2*ind+1].minus;
	}
}

void query1(int ind, int l, int r, int i_src, ll val){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

	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);
}

void query2(int ind, int l, int r, int l_src, int r_src){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

	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);
}

void query3(int ind, int l, int r, int l_src, int r_src){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

	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 7 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 229 ms 4224 KB Output is correct
2 Correct 183 ms 5672 KB Output is correct
3 Correct 212 ms 10596 KB Output is correct
4 Correct 228 ms 12756 KB Output is correct
5 Correct 260 ms 15456 KB Output is correct
6 Correct 273 ms 17832 KB Output is correct
7 Correct 295 ms 20352 KB Output is correct
8 Correct 269 ms 22820 KB Output is correct
9 Correct 226 ms 25056 KB Output is correct
10 Correct 247 ms 27364 KB Output is correct
11 Correct 251 ms 29808 KB Output is correct
12 Correct 289 ms 32108 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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