Submission #31848

#	Time	Username	Problem	Language	Result	Execution time	Memory
31848		YoLo	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	553 ms	12220 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75