oj.uz

Submission #31848

# Submission time Handle Problem Language Result Execution time Memory
31848 2017-09-11T04:15:59 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 553 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(K==1)
		return;
	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)
			upd(1, 1, n, l, r);
		else
			cout << getsum(1, 1, n, l, r) << endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12220 KB Output is correct
2 Correct 0 ms 12220 KB Output is correct
3 Correct 0 ms 12220 KB Output is correct
4 Correct 6 ms 12220 KB Output is correct
5 Correct 9 ms 12220 KB Output is correct
6 Correct 19 ms 12220 KB Output is correct
7 Correct 3 ms 12220 KB Output is correct
8 Correct 6 ms 12220 KB Output is correct
9 Correct 6 ms 12220 KB Output is correct
10 Correct 19 ms 12220 KB Output is correct
11 Correct 3 ms 12220 KB Output is correct
12 Correct 16 ms 12220 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 12220 KB Output is correct
2 Correct 246 ms 12220 KB Output is correct
3 Correct 219 ms 12220 KB Output is correct
4 Correct 173 ms 12220 KB Output is correct
5 Correct 219 ms 12220 KB Output is correct
6 Correct 266 ms 12220 KB Output is correct
7 Correct 346 ms 12220 KB Output is correct
8 Correct 373 ms 12220 KB Output is correct
9 Correct 283 ms 12220 KB Output is correct
10 Correct 233 ms 12220 KB Output is correct
11 Correct 363 ms 12220 KB Output is correct
12 Correct 226 ms 12220 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 12220 KB Output is correct
2 Correct 56 ms 12220 KB Output is correct
3 Correct 106 ms 12220 KB Output is correct
4 Correct 283 ms 12220 KB Output is correct
5 Correct 309 ms 12220 KB Output is correct
6 Correct 273 ms 12220 KB Output is correct
7 Correct 169 ms 12220 KB Output is correct
8 Correct 346 ms 12220 KB Output is correct
9 Correct 169 ms 12220 KB Output is correct
10 Correct 186 ms 12220 KB Output is correct
11 Correct 199 ms 12220 KB Output is correct
12 Correct 216 ms 12220 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 12220 KB Output is correct
2 Correct 353 ms 12220 KB Output is correct
3 Correct 349 ms 12220 KB Output is correct
4 Correct 399 ms 12220 KB Output is correct
5 Correct 406 ms 12220 KB Output is correct
6 Correct 553 ms 12220 KB Output is correct
7 Correct 313 ms 12220 KB Output is correct
8 Correct 499 ms 12220 KB Output is correct
9 Correct 443 ms 12220 KB Output is correct
10 Correct 513 ms 12220 KB Output is correct
11 Correct 509 ms 12220 KB Output is correct
12 Correct 526 ms 12220 KB Output is correct