oj.uz

Submission #50765

# Submission time Handle Problem Language Result Execution time Memory
50765 2018-06-13T07:33:43 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 126 ms 6320 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) push_pending(2*ind);
	if(segtree[2*ind+1].pending == 1) push_pending(2*ind+1);

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

void update_me(int ind){
	segtree[ind] = {0,0,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 4 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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