Submission #372341

#	Time	Username	Problem	Language	Result	Execution time	Memory
372341		luciocf	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	214 ms	9068 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;

int n, q, k;
int a[maxn];

struct FenwickTree
{
	ll bit[maxn];

	void upd(int x, int v)
	{
		for (; x < maxn; x += (x&-x))
			bit[x] += 1ll*v;
	}

	ll soma(int x)
	{
		ll ans = 0;
		for (; x > 0; x -= (x&-x))
			ans += bit[x];
		return ans;
	}

	ll get(int l, int r)
	{
		return soma(r)-soma(l-1);
	}
} BIT;

void solve1(void)
{
	while (q--)
	{
		int op, l, r;
		scanf("%d %d %d", &op, &l, &r);

		if (op == 1)
		{
			BIT.upd(l, r-a[l]);
			a[l] = r;
		}
		else if (op == 3)
		{
			printf("%lld\n", BIT.get(l, r));
		}
	}
}

int main(void)
{
	scanf("%d %d %d", &n, &q, &k);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		BIT.upd(i, a[i]);
	}

	if (k == 1)
	{
		solve1();
		return 0;
	}

	set<int> st;
	for (int i = 1; i <= n; i++)
		if (a[i] != 0)
			st.insert(i);

	while (q--)
	{
		int op, l, r;
		scanf("%d %d %d", &op, &l, &r);

		if (op == 1)
		{
			if (r != 0 && st.find(l) == st.end())
				st.insert(l);

			BIT.upd(l, r-a[l]);
			a[l] = r;
		}
		else if (op == 2)
		{
			for (auto it = st.lower_bound(l); it != st.end() && *it <= r; )
			{
				int p = *it;

				BIT.upd(p, a[p]/k - a[p]);
				a[p] /= k;

				if (a[p] == 0) it = st.erase(it);
				else it++;
			}
		}
		else
		{
			printf("%lld\n", BIT.get(l, r));
		}
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'void solve1()':
sterilizing.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   scanf("%d %d %d", &op, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d %d %d", &n, &q, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d %d %d", &op, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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