Submission #647642

#	Time	Username	Problem	Language	Result	Execution time	Memory
647642		ymm	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	249 ms	5332 KiB

sterilizing

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
ll seg[N<<2];
int n, q, k;

void spray(int l, int r, int k, int i, int b, int e)
{
	if (r <= b || e <= l)
		return;
	if (k == 1 || seg[i] == 0)
		return;
	if (e-b == 1) {
		seg[i] /= k;
		return;
	}
	spray(l,r,k,2*i+1,b,(b+e)/2);
	spray(l,r,k,2*i+2,(b+e)/2,e);
	seg[i] = seg[2*i+1] + seg[2*i+2];
}

void set_to(int p, ll x, int i, int b, int e)
{
	if (e-b == 1) {
		seg[i] = x;
		return;
	}
	if (p < (b+e)/2)
		set_to(p, x, 2*i+1, b, (b+e)/2);
	else
		set_to(p, x, 2*i+2, (b+e)/2, e);
	seg[i] = seg[2*i+1] + seg[2*i+2];
}

ll get(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r)
		return seg[i];
	if (r <= b || e <= l)
		return 0;
	return get(l,r,2*i+1,b,(b+e)/2) + get(l,r,2*i+2,(b+e)/2,e);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> q >> k;
	Loop (i,0,n) {
		int x;
		cin >> x;
		set_to(i, x, 0, 0, n);
	}
	while (q--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1)
			set_to(x-1, y, 0, 0, n);
		if (t == 2)
			spray(x-1, y, k, 0, 0, n);
		if (t == 3)
			cout << get(x-1, y, 0, 0, n) << '\n';
	}
}

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