oj.uz

Submission #31843

# Submission time Handle Problem Language Result Execution time Memory
31843 2017-09-11T04:01:08 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 609 ms 12220 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int lazy[402000], a[100009], n, m, K, f[402000], imax[402000];
void init(int k, int l, int r)
{
	if(l == r)
	{
		f[k] = a[l];
		imax[k] = a[l];
		return ;
	}
	int mid = (l + r) / 2;
	init(k * 2, l, mid);
	init(k * 2 + 1, mid + 1, r);
	f[k] = f[k * 2] + f[k * 2 + 1];
	imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
void upd(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return ;
	if(l == r)
	{
		f[k] = f[k] / K;
		imax[k] = f[k];
		return;
	}
	int mid = (l + r) / 2;
	if(imax[k * 2] > 0)
		upd(k * 2, l, mid, L, R);
	if(imax[k * 2 + 1] > 0)
		upd(k * 2 + 1, mid + 1, r, L, R);
	f[k] = f[k * 2] + f[k * 2 + 1];
	imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
void updd(int k, int l, int r, int pos, int val)
{
	if(r < pos || l > pos)
		return;
	if(l == pos && r == pos)
	{
		f[k] = val;
		imax[k] = f[k];
		return;
	}
	int mid = (l + r) / 2;
	updd(k * 2, l, mid, pos, val);
	updd(k * 2 + 1, mid + 1, r, pos, val);
	f[k] = f[k * 2] + f[k * 2 + 1];
	imax[k] = max(imax[k * 2], imax[k * 2 + 1]);
}
int getsum(int k, int l, int r, int L, int R)
{
	if(r < L || R < l || r < l)
		return 0;
	if(L <= l && r <= R)
		return f[k];
	int mid = (l + r) / 2;
	return getsum(k * 2, l, mid, L, R) + getsum(k * 2 + 1, mid + 1, r, L, R);
}
signed main()
{
	cin >> n >> m >> K;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	init(1, 1, n);
	while(m --)
	{
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1)
			updd(1, 1, n, l, r);
		else if(t == 2 && K != 1)
			upd(1, 1, n, l, r);
		else
			cout << getsum(1, 1, n, l, r) << endl;
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12220 KB Output is correct
2 Incorrect 9 ms 12220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12220 KB Output is correct
2 Correct 29 ms 12220 KB Output is correct
3 Correct 99 ms 12220 KB Output is correct
4 Correct 249 ms 12220 KB Output is correct
5 Correct 379 ms 12220 KB Output is correct
6 Correct 319 ms 12220 KB Output is correct
7 Incorrect 436 ms 12220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 12220 KB Output is correct
2 Correct 343 ms 12220 KB Output is correct
3 Correct 266 ms 12220 KB Output is correct
4 Correct 423 ms 12220 KB Output is correct
5 Correct 579 ms 12220 KB Output is correct
6 Correct 559 ms 12220 KB Output is correct
7 Correct 489 ms 12220 KB Output is correct
8 Correct 609 ms 12220 KB Output is correct
9 Correct 399 ms 12220 KB Output is correct
10 Correct 553 ms 12220 KB Output is correct
11 Correct 333 ms 12220 KB Output is correct
12 Correct 576 ms 12220 KB Output is correct