Submission #754840

#	Time	Username	Problem	Language	Result	Execution time	Memory
754840		raysh07	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	224 ms	8236 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF (int)(1e9)
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int n, q, k;
pair <int, int> seg[4 * N]; //{sum, mn}
int a[N];

void Build(int l, int r, int pos){
	if (l == r){
		seg[pos] = make_pair(a[l], a[l]);
		return;
	}

	int mid = (l + r)/2;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

void upd(int l, int r, int pos, int qp, int v){
	if (l == r){
		seg[pos] = make_pair(v, v);
		return;
	}

	int mid = (l + r)/2;
	if (qp <= mid) upd(l, mid, pos*2, qp, v);
	else upd(mid + 1, r, pos*2 + 1, qp, v);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

void divide(int l, int r, int pos, int ql, int qr){
	if (seg[pos].f == 0 || l > qr || r < ql) return;

	if (l == r){
		seg[pos].f /= k;
		seg[pos].s = seg[pos].f;
		return;
	}

	int mid = (l + r)/2;
	divide(l, mid, pos*2, ql, qr);
	divide(mid + 1, r, pos*2 + 1, ql, qr);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

int query(int l, int r, int pos, int ql, int qr){
	if (l >= ql && r <= qr) return seg[pos].f;
	else if (l > qr || r < ql) return 0;

	int mid = (l + r)/2;
	return query(l, mid, pos*2, ql, qr) + query(mid + 1, r, pos*2 + 1, ql, qr);
}

void Solve(){
	cin >> n >> q >> k;

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

	Build(1, n, 1);

	while (q--){
		int t; cin >> t;

		int x, y; cin >> x >> y;

		if (t == 1){
			upd(1, n, 1, x, y);
		} else if (t == 2){
			if (k != 1){
				divide(1, n, 1, x, y);
			}
		} else {
			cout << query(1, n, 1, x, y) << "\n";
		}
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1; 
	//cin >> t;
	
	while (t--) Solve();
	return 0;
}

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