Submission #828771

#	Time	Username	Problem	Language	Result	Execution time	Memory
828771		OAleksa	Sterilizing Spray (JOI15_sterilizing)	C++14	80 / 100	5080 ms	7704 KiB

sterilizing

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
#define int long long
const int maxn = 1e5 + 69;
const int lg = 30;
int st[4 * maxn], mx[4 * maxn];
int n, q, k, a[maxn];

void build(int v, int tl, int tr) {
	if(tl == tr) 
		st[v] = mx[v] = a[tl];
	else {
		int mid = (tl + tr) / 2;
		build(v * 2, tl, mid);
		build(v * 2 + 1, mid + 1, tr);
		st[v] = st[v * 2] + st[v * 2 + 1];
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
}

void upd(int v, int tl, int tr, int x, int y) {
	if(tl == tr) 
		st[v] = mx[v] = y;
	else {
		int mid = (tl + tr) / 2;
		if(x <= mid)
			upd(v * 2, tl, mid, x, y);
		else
			upd(v * 2 + 1, mid + 1, tr, x, y);
		st[v] = st[v * 2] + st[v * 2 + 1];
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
}

void sprejamVamPoKevama(int v, int tl, int tr, int l, int r) {
	if(tl > r || tr < l)
		return;
	else if(tl >= l && tr <= r) {
		if(mx[v] > 0) {
			if(tl == tr)
				st[v] /= k, mx[v] /= k;
			else {
				int mid = (tl + tr) / 2;
				sprejamVamPoKevama(v * 2, tl, mid, l, r);
				sprejamVamPoKevama(v * 2 + 1, mid + 1, tr, l, r);
				st[v] = st[v * 2] + st[v * 2 + 1];
				mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
			}
		}
		return;
	}
	int mid = (tl + tr) / 2;
	sprejamVamPoKevama(v * 2, tl, mid, l, r);
	sprejamVamPoKevama(v * 2 + 1, mid + 1, tr, l, r);
	st[v] = st[v * 2] + st[v * 2 + 1];
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}

int brojimKeve(int v, int tl, int tr, int l, int r) {
	if(tl > r || tr < l)
		return 0; //no bitches
	else if(tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return brojimKeve(v * 2, tl, mid, l, r) + brojimKeve(v * 2 + 1, mid + 1, tr, l, r);
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> q >> k;
		for(int i = 1;i <= n;i++)
			cin >> a[i];
		build(1, 1, n);
		for(int i = 1;i <= q;i++) {
			int t, a, b;
			cin >> t >> a >> b;
			if(t == 1) 
				upd(1, 1, n, a, b);
			else if(t == 2) 
				sprejamVamPoKevama(1, 1, n, a, b);
			else 
				cout << brojimKeve(1, 1, n, a, b) << "\n";
		}
	}
   return 0;
}

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