oj.uz

Submission #50779

# Submission time Handle Problem Language Result Execution time Memory
50779 2018-06-13T08:03:01 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 271 ms 14056 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;
	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(BTW(l, l_src, r_src) && BTW(r, l_src, 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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 4200 KB Output is correct
2 Correct 209 ms 4200 KB Output is correct
3 Correct 196 ms 7272 KB Output is correct
4 Correct 216 ms 7656 KB Output is correct
5 Correct 271 ms 7656 KB Output is correct
6 Correct 237 ms 7656 KB Output is correct
7 Correct 255 ms 7656 KB Output is correct
8 Correct 242 ms 7760 KB Output is correct
9 Runtime error 130 ms 14056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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