oj.uz

Submission #372341

# Submission time Handle Problem Language Result Execution time Memory
372341 2021-02-27T17:43:28 Z luciocf Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 214 ms 9068 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 5 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 5 ms 620 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 4 ms 620 KB Output is correct
11 Correct 5 ms 620 KB Output is correct
12 Correct 5 ms 620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3260 KB Output is correct
2 Correct 40 ms 2796 KB Output is correct
3 Correct 36 ms 3180 KB Output is correct
4 Correct 46 ms 3948 KB Output is correct
5 Correct 68 ms 4460 KB Output is correct
6 Correct 56 ms 4460 KB Output is correct
7 Correct 54 ms 4460 KB Output is correct
8 Correct 57 ms 4460 KB Output is correct
9 Correct 54 ms 4332 KB Output is correct
10 Correct 54 ms 4332 KB Output is correct
11 Correct 53 ms 4332 KB Output is correct
12 Correct 59 ms 4480 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1004 KB Output is correct
2 Correct 18 ms 2156 KB Output is correct
3 Correct 22 ms 2412 KB Output is correct
4 Correct 42 ms 2412 KB Output is correct
5 Correct 65 ms 5356 KB Output is correct
6 Correct 64 ms 5356 KB Output is correct
7 Correct 49 ms 3052 KB Output is correct
8 Correct 64 ms 5320 KB Output is correct
9 Correct 61 ms 5228 KB Output is correct
10 Correct 65 ms 5228 KB Output is correct
11 Correct 63 ms 5228 KB Output is correct
12 Correct 61 ms 5228 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5228 KB Output is correct
2 Correct 81 ms 5356 KB Output is correct
3 Correct 94 ms 4332 KB Output is correct
4 Correct 88 ms 4204 KB Output is correct
5 Correct 125 ms 9068 KB Output is correct
6 Correct 134 ms 8940 KB Output is correct
7 Correct 125 ms 8940 KB Output is correct
8 Correct 167 ms 8940 KB Output is correct
9 Correct 141 ms 8812 KB Output is correct
10 Correct 166 ms 8812 KB Output is correct
11 Correct 129 ms 8812 KB Output is correct
12 Correct 214 ms 8812 KB Output is correct