Submission #342277

#	Time	Username	Problem	Language	Result	Execution time	Memory
342277		Nursik	Sterilizing Spray (JOI15_sterilizing)	C++14	15 / 100	5033 ms	3564 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;
ll a[N];
ll f[N];
int type;
void upd(int pos, ll val)
{
	for (int i = pos; i <= n; i |= (i + 1))
	{
		f[i] += val;
	}
}
ll get(int pos)
{
	ll res = 0;
	for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
	{
		res += f[i];
	}
	return res;
}
int t[N * 4], m[N * 4];
void upd2(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
	{
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		upd2(pos, val, v * 2, tl, tm);
	else
		upd2(pos, val, v * 2 + 1, tm + 1, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v)
{
	if (m[v])
	{
		t[v * 2] = t[v];
		t[v * 2 + 1] = t[v];
		m[v * 2] = m[v];
		m[v * 2 + 1] = m[v];
		m[v] = 0;
	}
}
int get3(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v);
	if (l <= tl && tr <= r)
		return t[v];
	if (l > tl || r < tl)
		return 0;
	int tm = (tl + tr) / 2;
	t[v] = t[v + v] + t[v + v + 1];
	return get3(l, r, v * 2, tl, tm) + get3(l, r, v * 2 + 1, tm + 1, tr);
}
void get2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v);
	if (l <= tl && tr <= r)
	{
		m[v] = 1;
		t[v] = 0;
		push(v);
		return;
	}
	if (l > tr || r < tl)
		return;
	int tm = (tl + tr) / 2;
	get2(l, r, v * 2, tl, tm);
	get2(l, r, v * 2 + 1, tm + 1, tr);
}
int main()
{
	data();     
	cin >> n >> q >> k;
	int check = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
		upd2(i, a[i]);
		check = (check | (a[i] > 1));
	}   
	//subtask 3
	if (check == 0)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				a[pos] = x;
				upd2(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
				if (k > 1)
				{
					get2(l, r);
				}
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get3(l, r) << '\n';
			}
		}
		return 0;	
	}
	//subtask 2
	if (k == 1)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				upd(pos, -a[pos]);
				a[pos] = x;
				upd(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get(r) - get(l - 1) << '\n';
			}
		}
		return 0;
	}
	//subtask 1
	for (int i = 1; i <= q; i++)
	{
		cin >> type;
		if (type == 1)
		{
			int pos, x;
			cin >> pos >> x;
			upd(pos, -a[pos]);
			a[pos] = x;
			upd(pos, x);
		}
		else if (type == 2)
		{
			int l, r;
			cin >> l >> r;
			for (int j = l; j <= r; j++)
			{
				upd(j, -a[j]);
				upd(j, a[j] / k);
				a[j] /= k;
			}
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << get(r) - get(l - 1) << '\n';
		}	
	}  
}
/*           
*/

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