oj.uz

Submission #31830

# Submission time Handle Problem Language Result Execution time Memory
31830 2017-09-11T03:23:37 Z YoLo Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 586 ms 9076 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];
void init(int k, int l, int r)
{
	lazy[k] = 1;
	if(l == r)
	{
		f[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];
}
void dolazy(int k, int l, int r)
{
	f[k] = f[k] / lazy[k];
	if(l < r)
	{
		lazy[k * 2] = min(lazy[k * 2] * lazy[k], mod);
		lazy[k * 2 + 1] = min(lazy[k * 2 + 1] * lazy[k], mod);
	}
	lazy[k] = 1;
}
void upd(int k, int l, int r, int L, int R)
{
	dolazy(k, l, r);
	if(r < L || R < l || r < l)
		return ;
	if(L <= l && r <= R)
	{
		f[k] = f[k] / K;
		if(l < r)
		{
			lazy[k * 2] = min(lazy[k * 2] * K, mod);
			lazy[k * 2 + 1] = min(lazy[k * 2 + 1] * K, mod);
		}
		return ;
	}
	int mid = (l + r) / 2;
	upd(k * 2, l, mid, L, R);
	upd(k * 2 + 1, mid + 1, r, L, R);
	f[k] = f[k * 2] + f[k * 2 + 1];
}
void updd(int k, int l, int r, int pos, int val)
{
	dolazy(k, l, r);
	if(r < pos || l > pos)
		return;
	if(l == pos && r == pos)
	{
		f[k] = val;
		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];
}
int getsum(int k, int l, int r, int L, int R)
{
	dolazy(k, l, 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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 9076 KB Output is correct
2 Correct 356 ms 9076 KB Output is correct
3 Correct 279 ms 9076 KB Output is correct
4 Correct 516 ms 9076 KB Output is correct
5 Correct 413 ms 9076 KB Output is correct
6 Correct 549 ms 9076 KB Output is correct
7 Correct 426 ms 9076 KB Output is correct
8 Correct 586 ms 9076 KB Output is correct
9 Correct 466 ms 9076 KB Output is correct
10 Correct 433 ms 9076 KB Output is correct
11 Correct 333 ms 9076 KB Output is correct
12 Correct 523 ms 9076 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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