oj.uz

Submission #40890

# Submission time Handle Problem Language Result Execution time Memory
40890 2018-02-09T19:49:30 Z MatheusLealV Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 109 ms 4016 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;

int n, q, k, 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]);
}

int 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++)
	{
		int op, a, b, c;

		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";
	}
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:78:17: warning: unused variable 'c' [-Wunused-variable]
   int op, a, b, c;
                 ^

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
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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