Submission #342307

#	Time	Username	Problem	Language	Result	Execution time	Memory
342307		Nursik	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	366 ms	5868 KiB

sterilizing

#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
}
void speed_force() {
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
} 
                     
int n, q, k, type, l, r;
ll a[N], t[N * 4], t2[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
	{
		t[v] = val;
		t2[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		upd(pos, val, v * 2, tl, tm);
	else
		upd(pos, val, v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
	t2[v] = t2[v + v] + t2[v + v + 1];
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if (l <= tl && tr <= r)
		return t2[v];
	if (l > tr || r < tl)
		return 0;
	int tm = (tl + tr) / 2;
	return get(l, r, v * 2, tl, tm) + get(l, r, v * 2 + 1, tm + 1, tr);
}
void upd2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if (l > tr || r < tl || t[v] == 0)
		return;
	if (tl == tr)
	{
		t[v] = t[v] / k, t2[v] = t2[v] / k;
		return;
	}
	int tm = (tl + tr) / 2;
	upd2(l, r, v * 2, tl, tm);
	upd2(l, r, v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
	t2[v] = t2[v + v] + t2[v + v + 1];
}
int main()
{
	data();
	speed_force();     
	cin >> n >> q >> k;  
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
	}
	for (int i = 1; i <= q; i++)
	{
		cin >> type;
		if (type == 1)
		{
			int pos, x;
			cin >> pos >> x;
			upd(pos, x);
		}
		else if (type == 2)
		{
			cin >> l >> r;
			if (k > 1)
			{
				upd2(l, r);
			}
		}
		else
		{
			cin >> l >> r;
			cout << get(l, r) << '\n';
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75