Submission #380519

#	Time	Username	Problem	Language	Result	Execution time	Memory
380519		pure_mem	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	337 ms	7404 KiB

sterilizing

#include <bits/stdc++.h>
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 1e5 + 12;
const ll INF = 1e18;

ll t1[N * 4], t2[N * 4]; 
int n, q, k;
void build(int v, int tl, int tr){
	if(tl == tr){
		cin >> t1[v], t2[v] = t1[v];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm), build(v * 2 + 1, tm + 1, tr);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
void upd(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		if(tl == tr){
			t1[v] /= k, t2[v] = t1[v];
			return;
		}
		else if(t2[v] == 0){
			return;
		}
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r);
	upd(v * 2 + 1, tm + 1, tr, l, r);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
void upd1(int v, int tl, int tr, int pos){
	if(tl == tr){
		cin >> t1[v], t2[v] = t1[v];
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)
		upd1(v * 2, tl, tm, pos);
	else
		upd1(v * 2 + 1, tm + 1, tr, pos);
	t1[v] = t1[v * 2] + t1[v * 2 + 1];
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
ll get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return t1[v];
	int tm = (tl + tr) / 2;
	return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q >> k, build(1, 1, n);
	for(int tc, l, r;q--;){
		cin >> tc >> l;
		if(tc == 1){
			upd1(1, 1, n, l);
		}	
		else if(tc == 2){
			cin >> r;
			if(k > 1)
				upd(1, 1, n, l, r);
		}
		else{
			cin >> r, cout << get(1, 1, n, l, r) << "\n";
		}
	}
}

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