oj.uz

Submission #31839

# Submission time Handle Problem Language Result Execution time Memory
31839 2017-09-11T03:51:02 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 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)
			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 13 ms 12220 KB Output is correct
2 Correct 3 ms 12220 KB Output is correct
3 Correct 3 ms 12220 KB Output is correct
4 Correct 3 ms 12220 KB Output is correct
5 Correct 6 ms 12220 KB Output is correct
6 Correct 13 ms 12220 KB Output is correct
7 Correct 9 ms 12220 KB Output is correct
8 Correct 6 ms 12220 KB Output is correct
9 Correct 13 ms 12220 KB Output is correct
10 Correct 6 ms 12220 KB Output is correct
11 Correct 6 ms 12220 KB Output is correct
12 Correct 3 ms 12220 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 12220 KB Output is correct
2 Correct 39 ms 12220 KB Output is correct
3 Correct 93 ms 12220 KB Output is correct
4 Correct 186 ms 12220 KB Output is correct
5 Correct 206 ms 12220 KB Output is correct
6 Correct 299 ms 12220 KB Output is correct
7 Execution timed out 5000 ms 12220 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12220 KB Output is correct
2 Correct 326 ms 12220 KB Output is correct
3 Correct 246 ms 12220 KB Output is correct
4 Correct 296 ms 12220 KB Output is correct
5 Correct 369 ms 12220 KB Output is correct
6 Correct 393 ms 12220 KB Output is correct
7 Correct 419 ms 12220 KB Output is correct
8 Correct 466 ms 12220 KB Output is correct
9 Correct 539 ms 12220 KB Output is correct
10 Correct 539 ms 12220 KB Output is correct
11 Correct 326 ms 12220 KB Output is correct
12 Correct 589 ms 12220 KB Output is correct