Submission #88130

#	Time	Username	Problem	Language	Result	Execution time	Memory
88130		KCSC	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	444 ms	70876 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

struct Node {
	int mxm;
	long long sum; } sgt[DIM << 2];

void update1(int nd, int le, int ri, int ps, int vl) {
	if (le == ri) {
		sgt[nd] = {vl, vl}; }
	else {
		int md = (le + ri) / 2;
		if (ps <= md) {
			update1(nd << 1, le, md, ps, vl); }
		else {
			update1(nd << 1 | 1, md + 1, ri, ps, vl); }
		sgt[nd] = {max(sgt[nd << 1].mxm, sgt[nd << 1 | 1].mxm),
				   sgt[nd << 1].sum + sgt[nd << 1 | 1].sum}; } }

void update2(int nd, int le, int ri, int st, int en, int k) {
	if (sgt[nd].mxm == 0 or k == 1) {
		return; }
	if (le == ri) {
		sgt[nd] = {sgt[nd].mxm / k, sgt[nd].mxm / k}; }
	else {
		int md = (le + ri) / 2;
		if (st <= md) {
			update2(nd << 1, le, md, st, en, k); }
		if (md <  en) {
			update2(nd << 1 | 1, md + 1, ri, st, en, k); }
		sgt[nd] = {max(sgt[nd << 1].mxm, sgt[nd << 1 | 1].mxm),
				   sgt[nd << 1].sum + sgt[nd << 1 | 1].sum}; } } 

long long query(int nd, int le, int ri, int st, int en) {
	if (st <= le and ri <= en) {
		return sgt[nd].sum; }
	else {
		int md = (le + ri) / 2;
		if (en <= md) {	
			return query(nd << 1, le, md, st, en); }
		if (md <  st) {
			return query(nd << 1 | 1, md + 1, ri, st, en); }
		return query(nd << 1, le, md, st, en) +
			   query(nd << 1 | 1, md + 1, ri, st, en); } }

int main(void) {
#ifdef HOME
	freopen("sterilizing.in", "r", stdin);
	freopen("sterilizing.out", "w", stdout);
#endif
	int n, q, k; cin >> n >> q >> k;
	for (int i = 1; i <= n; ++i) {		
		int x; cin >> x; update1(1, 1, n, i, x); }
	while (q--) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) {
			update1(1, 1, n, x, y); }
		if (t == 2) {	
			update2(1, 1, n, x, y, k); }
		if (t == 3) {
			cout << query(1, 1, n, x, y) << "\n"; } }		
	return 0; }

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