oj.uz

Submission #50785

# Submission time Handle Problem Language Result Execution time Memory
50785 2018-06-13T10:13:09 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 7932 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, 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 push_pending(int ind){
	if(ind > MAKSI) return;

	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].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){
	//cout << "Q2 " << ind << " " << l << " " << r << endl;

	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);
	//cout << MAKSI << endl;
	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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 7132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 7132 KB Output is correct
2 Correct 3874 ms 7460 KB Output is correct
3 Execution timed out 5059 ms 7844 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 7932 KB Time limit exceeded
2 Halted 0 ms 0 KB -