oj.uz

Submission #31846

# Submission time Handle Problem Language Result Execution time Memory
31846 2017-09-11T04:04:19 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 643 ms 12220 KB 
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl '\n'
#define pi acos(-1)
#define pque priority_queue
typedef pair < int, int > ii;
typedef vector < int > vi;
typedef vector < vi > vii;
int mod = 1000000007;
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 0 ms 12220 KB Output is correct
2 Incorrect 3 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 393 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 89 ms 12220 KB Output is correct
2 Correct 46 ms 12220 KB Output is correct
3 Correct 86 ms 12220 KB Output is correct
4 Correct 259 ms 12220 KB Output is correct
5 Correct 203 ms 12220 KB Output is correct
6 Correct 403 ms 12220 KB Output is correct
7 Incorrect 313 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 209 ms 12220 KB Output is correct
2 Correct 273 ms 12220 KB Output is correct
3 Correct 356 ms 12220 KB Output is correct
4 Correct 289 ms 12220 KB Output is correct
5 Correct 496 ms 12220 KB Output is correct
6 Correct 429 ms 12220 KB Output is correct
7 Correct 313 ms 12220 KB Output is correct
8 Correct 589 ms 12220 KB Output is correct
9 Correct 366 ms 12220 KB Output is correct
10 Correct 643 ms 12220 KB Output is correct
11 Correct 489 ms 12220 KB Output is correct
12 Correct 546 ms 12220 KB Output is correct