Submission #1034125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034125		juicy	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	80 ms	64916 KiB

sterilizing

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 1e5 + 5, LG = 30;
 
int n, q, k;
int lz[4 * N];
long long s[4 * N][LG];
 
void pull(int id) {
	for (int j = 0; j < (k > 1 ? LG : 1); ++j) {
		s[id][j] = s[id * 2][j] + s[id * 2 + 1][j];
	}
}
 
void app(int id, int x) {
	x = min(x, LG);
	if (x == LG) {
		fill(s[id], s[id] + LG, 0);
	} else {
		for (int i = 0; i + x < LG; ++i) {
			s[id][i] = s[id][i + x];
			s[id][i + x] = 0;
		}
	}
}
 
void psh(int id) {
	assert(!lz[id]);
	if (lz[id]) {
		app(id * 2, lz[id]);
		app(id * 2 + 1, lz[id]);
		lz[id] = 0;
	}
}
 
void upd(int i, int x, int id = 1, int l = 1, int r = n) {
	if (l == r) {
		s[id][0] = x;
		if (k > 1) {
			for (int i = 1; i < LG; ++i) {
				x /= k;
				s[id][i] = x;
			}
		}
		return;
	}
	psh(id);
	int md = (l + r) / 2;
	if (i <= md) {
		upd(i, x, id * 2, l, md);
	} else {
		upd(i, x, id * 2 + 1, md + 1, r);
	}
	pull(id);
}
 
void spray(int u, int v, int id = 1, int l = 1, int r = n) {
	if (u <= l && r <= v) {
		app(id, 1);
		return;
	}
	int md = (l + r) / 2;
	if (u <= md) {
		spray(u, v, id * 2, l, md);
	}
	if (md < v) {
		spray(u, v, id * 2 + 1, md + 1, r);
	}
	pull(id);
}
 
long long qry(int u, int v, int id = 1, int l = 1, int r = n) {
	if (u <= l && r <= v) {
		return s[id][0];
	}
	psh(id);
	int md = (l + r) / 2;
	if (v <= md) {
		return qry(u, v, id * 2, l, md);
	}
	if (md < u) {
		return qry(u, v, id * 2 + 1, md + 1, r);
	}
	return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	cin >> n >> q >> k;
	assert(k == 1);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		upd(i, x);
	}	
	while (q--) {
		int type, a, b; cin >> type >> a >> b;
		if (type == 1) {
			upd(a, b);
		} else if (type == 2) {
			if (k > 1) {
				spray(a, b, 1);
			}
		} else {
			cout << qry(a, b) << "\n";
		}
	}
	return 0;
}

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