Submission #31827

#	Time	Username	Problem	Language	Result	Execution time	Memory
31827		YoLo	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	349 ms	6112 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[202000], a[100009], n, m, K, f[202000];
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()
{
	ios_base::sync_with_stdio(0);
	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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75