oj.uz

Submission #40892

# Submission time Handle Problem Language Result Execution time Memory
40892 2018-02-09T20:09:20 Z MatheusLealV Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 388 ms 14028 KB 
#include <bits/stdc++.h>
#define N 100005
#define l (2*nod)
#define r ((2*nod) + 1)
#define mid ((a + b)/2)
using namespace std;
typedef long long ll;

int n, q, k;

ll max_tree[4*N][2], v[N];

void upd(int nod, int a, int b, int i, ll x)
{
	if(a == b) max_tree[nod][0] = max_tree[nod][1] = x;

	else
	{
		if(i <= mid) upd(l, a, mid, i, x);

		else upd(r, mid + 1, b, i, x);

		max_tree[nod][0] = max_tree[l][0] + max_tree[r][0];

		max_tree[nod][1] = max(max_tree[l][1], max_tree[r][1]);
	}
}

void upd2(int nod, int a, int b, int i, int j)
{
	if(i > b || j < a) return;

	if(!max_tree[nod][1]) return;

	if(a == b)
	{
		max_tree[nod][0] /= k;

		max_tree[nod][1] /= k;

		return;
	}

	upd2(l, a, mid, i, j), upd2(r, mid + 1, b, i, j);

	max_tree[nod][0] = max_tree[l][0] + max_tree[r][0];

	max_tree[nod][1] = max(max_tree[l][1], max_tree[r][1]);
}

ll query(int nod, int a, int b, int i, int j)
{
	if(i <= a && j >= b) return max_tree[nod][0];

	if(i > b || j < a) return 0;

	return query(l, a, mid, i, j) + query(r, mid + 1, b, i, j);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q>>k;

	for(int i = 1; i <= n; i++) cin>>v[i], upd(1, 1, n, i, v[i]);

	for(int i = 0; i < q; i++)
	{
		ll op, a, b;

		cin>>op>>a>>b;

		if(op == 1) upd(1, 1, n, a, b);

		if(op == 2 && k >= 2) upd2(1, 1, n, a, b);

		if(op == 3) cout<<query(1, 1, n, a, b)<<"\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 6 ms 696 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 6 ms 852 KB Output is correct
8 Correct 6 ms 852 KB Output is correct
9 Correct 8 ms 852 KB Output is correct
10 Correct 7 ms 852 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 6 ms 852 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3632 KB Output is correct
2 Correct 56 ms 3632 KB Output is correct
3 Correct 59 ms 5680 KB Output is correct
4 Correct 71 ms 5844 KB Output is correct
5 Correct 88 ms 6064 KB Output is correct
6 Correct 93 ms 6064 KB Output is correct
7 Correct 96 ms 6064 KB Output is correct
8 Correct 87 ms 6064 KB Output is correct
9 Correct 79 ms 6064 KB Output is correct
10 Correct 84 ms 6064 KB Output is correct
11 Correct 77 ms 6064 KB Output is correct
12 Correct 75 ms 6064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6064 KB Output is correct
2 Correct 21 ms 6064 KB Output is correct
3 Correct 31 ms 6064 KB Output is correct
4 Correct 61 ms 6064 KB Output is correct
5 Correct 88 ms 6064 KB Output is correct
6 Correct 99 ms 6064 KB Output is correct
7 Correct 83 ms 7088 KB Output is correct
8 Correct 91 ms 8512 KB Output is correct
9 Correct 82 ms 9808 KB Output is correct
10 Correct 98 ms 10952 KB Output is correct
11 Correct 82 ms 12224 KB Output is correct
12 Correct 82 ms 13624 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 13624 KB Output is correct
2 Correct 126 ms 13624 KB Output is correct
3 Correct 165 ms 13624 KB Output is correct
4 Correct 156 ms 13624 KB Output is correct
5 Correct 197 ms 13828 KB Output is correct
6 Correct 221 ms 13828 KB Output is correct
7 Correct 185 ms 13828 KB Output is correct
8 Correct 283 ms 13936 KB Output is correct
9 Correct 230 ms 13936 KB Output is correct
10 Correct 268 ms 13936 KB Output is correct
11 Correct 199 ms 13936 KB Output is correct
12 Correct 388 ms 14028 KB Output is correct