oj.uz

Submission #40891

# Submission time Handle Problem Language Result Execution time Memory
40891 2018-02-09T19:54:14 Z MatheusLealV Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 129 ms 30472 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 tree[4*N][2], v[N];

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

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

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

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

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

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

	if(tree[nod][1] <= 1 && i <= a && j >= b)
	{
		tree[nod][1] = 0;

		tree[nod][0] = 0;

		//cout<<"SET UPDATE "<<a<<" "<<b<<"\n";

		return;
	}

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

		tree[nod][1] /= k;

		return;
	}

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

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

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

ll query(int nod, int a, int b, int i, int j)
{
	//if(i == 3 && j == 5) cout<<a<<" "<<b<<" "<<tree[nod][0]<<"\n";

	if(i <= a && j >= b) return 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) upd2(1, 1, n, a, b);

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3424 KB Output is correct
2 Correct 54 ms 4796 KB Output is correct
3 Correct 56 ms 8800 KB Output is correct
4 Correct 71 ms 11164 KB Output is correct
5 Correct 82 ms 13796 KB Output is correct
6 Correct 83 ms 16264 KB Output is correct
7 Correct 111 ms 18764 KB Output is correct
8 Correct 83 ms 21244 KB Output is correct
9 Correct 78 ms 23572 KB Output is correct
10 Correct 79 ms 25856 KB Output is correct
11 Correct 80 ms 28172 KB Output is correct
12 Correct 80 ms 30472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 30472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 30472 KB Output isn't correct
2 Halted 0 ms 0 KB -