Submission #647642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
647642	2022-10-03T12:55:23 Z	ymm	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	249 ms	5332 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 ms	340 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	4 ms	472 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	4 ms	428 KB	Output is correct
12	Correct	3 ms	468 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	3632 KB	Output is correct
2	Correct	42 ms	3304 KB	Output is correct
3	Correct	41 ms	4312 KB	Output is correct
4	Correct	53 ms	4804 KB	Output is correct
5	Correct	66 ms	5196 KB	Output is correct
6	Correct	62 ms	5232 KB	Output is correct
7	Correct	63 ms	5332 KB	Output is correct
8	Correct	63 ms	5232 KB	Output is correct
9	Correct	60 ms	5048 KB	Output is correct
10	Correct	60 ms	5048 KB	Output is correct
11	Correct	60 ms	5112 KB	Output is correct
12	Correct	61 ms	5072 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	928 KB	Output is correct
2	Correct	15 ms	1636 KB	Output is correct
3	Correct	26 ms	1748 KB	Output is correct
4	Correct	46 ms	2008 KB	Output is correct
5	Correct	64 ms	3892 KB	Output is correct
6	Correct	63 ms	3780 KB	Output is correct
7	Correct	55 ms	3900 KB	Output is correct
8	Correct	64 ms	3772 KB	Output is correct
9	Correct	58 ms	3640 KB	Output is correct
10	Correct	60 ms	3612 KB	Output is correct
11	Correct	62 ms	3684 KB	Output is correct
12	Correct	58 ms	3592 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	3032 KB	Output is correct
2	Correct	87 ms	3196 KB	Output is correct
3	Correct	111 ms	2576 KB	Output is correct
4	Correct	116 ms	2804 KB	Output is correct
5	Correct	134 ms	5052 KB	Output is correct
6	Correct	153 ms	5048 KB	Output is correct
7	Correct	130 ms	5036 KB	Output is correct
8	Correct	180 ms	5036 KB	Output is correct
9	Correct	170 ms	4892 KB	Output is correct
10	Correct	186 ms	4940 KB	Output is correct
11	Correct	142 ms	5120 KB	Output is correct
12	Correct	249 ms	5000 KB	Output is correct