Submission #1291867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291867		Jawad_Akbar_JJ	Sterilizing Spray (JOI15_sterilizing)	C++20	15 / 100	5094 ms	2608 KiB

sterilizing

#include <iostream>

using namespace std;

const int N = (1<<17) + 1;
long long sum[N<<1], k;

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (en - st == 1){
		sum[cur] = vl;
		return;
	}
	int lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;

	if (i < mid)
		insert(i, vl, lc, st, mid);
	else
		insert(i, vl, rc, mid, en);
	sum[cur] = sum[lc] + sum[rc];
}

void oper(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return;
	if (en - st == 1){
		sum[cur] /= k;
		return;
	}
	int lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;

	oper(l, r, lc, st, mid);
	oper(l, r, rc, mid, en);
	sum[cur] = sum[lc] + sum[rc];
}

long long get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return sum[cur];
	int lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;
	return get(l, r, lc, st, mid) + get(l, r, rc, mid, en);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, q;
	cin>>n>>q>>k;

	for (int i=1, a;i<=n;i++){
		cin>>a;
		insert(i, a);
	}

	for (int i=1;i<=q;i++){
		int t, l, r;
		cin>>t>>l>>r;

		if (t == 1)
			insert(l, r);
		else if (t == 2){
			if (k != 1)
				oper(l, r + 1);
		}
		else
			cout<<get(l, r+1)<<'\n';
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75