oj.uz

Submission #620573

# Submission time Handle Problem Language Result Execution time Memory
620573 2022-08-03T07:15:09 Z 장태환(#8519) Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1287 ms 70184 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int stree[1 << 18][35];
int lazyv[1 << 18];
int lazyc[1 << 18];
int dv[35];
int treeN;
int N, K;
void ul(int n,int siz)
{
	siz++;
	if (lazyv[n] != -1)
	{
		int i;
		for (i = 0; i < 35; i++)
		{
			stree[n][i] = siz * (lazyv[n]/dv[i]);
		}
		if (n < treeN)
		{
			lazyv[n * 2] = lazyv[n];
			lazyv[n * 2 + 1] = lazyv[n];
		}
		lazyv[n] = -1;
	}
	if (K == 1)
		lazyc[n] = 0;
	int nstree[35] = { 0 };
	int i;
	for (i = 0; i < 35 - lazyc[n]; i++)
	{
		nstree[i] = stree[n][i +lazyc[n]];
	}
	for (i = 0; i < 35; i++)
		stree[n][i] = nstree[i];
	if (n < treeN)
	{
		lazyc[n * 2] += lazyc[n];
		lazyc[n * 2 + 1] += lazyc[n];
	}
	lazyc[n] = 0;
}
void upd1(int qs, int qe, int v, int s = 0, int e = treeN - 1, int i = 1)
{
	ul(i, e - s);
	if (qs > e || s > qe)
	{
		return;
	}
	if (qs <= s && e <= qe)
	{
		lazyv[i] = v;
		ul(i, e - s);
		return;
	}
	upd1(qs, qe, v, s, (s + e) / 2, i * 2);
	upd1(qs, qe, v, (s + e) / 2 + 1, e, i * 2 + 1);
	int j;
	for (j = 0; j < 35; j++)
	{
		stree[i][j] = stree[i * 2][j] + stree[i * 2 + 1][j];
	}
}
void upd2(int qs, int qe, int s = 0, int e = treeN - 1, int i = 1)
{
	ul(i, e - s);
	if (qs > e || s > qe)
	{
		return;
	}
	if (qs <= s && e <= qe)
	{
		lazyc[i] = 1;
		ul(i, e - s);
		return;
	}
	upd2(qs, qe, s, (s + e) / 2, i * 2);
	upd2(qs, qe, (s + e) / 2 + 1, e, i * 2 + 1);
	int j;
	for (j = 0; j < 35; j++)
	{
		stree[i][j] = stree[i * 2][j] + stree[i * 2 + 1][j];
	}
}
int ge(int qs, int qe, int s = 0, int e = treeN - 1, int i = 1)
{
	ul(i, e - s);
	if (qs > e || s > qe)
	{
		return 0;
	}
	if (qs <= s && e <= qe)
	{
		return stree[i][0];
	}
	return ge(qs, qe, s, (s + e) / 2, i * 2) + ge(qs, qe, (s + e) / 2 + 1, e, i * 2 + 1);
}
signed main()
{
	int N, Q;
	cin >> N >> Q >> K;
	for (treeN = 1; treeN <= N; treeN *= 2);
	int i;
	memset(lazyv, -1, sizeof(lazyv));
	dv[0] = 1;
	for (i = 1; i < 35; i++)
	{
		dv[i] = min(dv[i-1] * K, 1LL << 55);
	}
	for (i = 1; i <= N; i++)
	{
		int a;
		cin >> a;
		lazyv[i + treeN] = a;
		ul(i + treeN, 0);
	}
	for (i = treeN - 1; i > 0; i--)
	{
		int j;
		for (j = 0; j < 35; j++)
		{
			stree[i][j] = stree[i * 2][j] + stree[i * 2 + 1][j];
		}
	}
	

	for (i = 0; i < Q; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1)
		{
			upd1(b, b, c);
		}
		else if (a == 2)
		{
			upd2(b, c);
		}
		else
		{
			cout << ge(b, c) << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2388 KB Output is correct
2 Correct 6 ms 2772 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 14 ms 3284 KB Output is correct
5 Correct 16 ms 4448 KB Output is correct
6 Correct 17 ms 4444 KB Output is correct
7 Correct 17 ms 4436 KB Output is correct
8 Correct 18 ms 4448 KB Output is correct
9 Correct 19 ms 4444 KB Output is correct
10 Correct 17 ms 4448 KB Output is correct
11 Correct 17 ms 4436 KB Output is correct
12 Correct 17 ms 4436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 36896 KB Output is correct
2 Correct 575 ms 32176 KB Output is correct
3 Correct 519 ms 62536 KB Output is correct
4 Correct 671 ms 69424 KB Output is correct
5 Correct 865 ms 70184 KB Output is correct
6 Correct 867 ms 70152 KB Output is correct
7 Correct 1287 ms 70172 KB Output is correct
8 Correct 943 ms 70184 KB Output is correct
9 Correct 770 ms 70000 KB Output is correct
10 Correct 758 ms 70064 KB Output is correct
11 Correct 735 ms 69964 KB Output is correct
12 Correct 693 ms 70024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 6940 KB Output is correct
2 Correct 115 ms 33608 KB Output is correct
3 Correct 165 ms 33656 KB Output is correct
4 Correct 510 ms 19624 KB Output is correct
5 Correct 685 ms 68740 KB Output is correct
6 Correct 652 ms 68740 KB Output is correct
7 Correct 693 ms 68820 KB Output is correct
8 Correct 668 ms 68736 KB Output is correct
9 Correct 632 ms 68568 KB Output is correct
10 Correct 586 ms 68656 KB Output is correct
11 Correct 613 ms 68684 KB Output is correct
12 Correct 596 ms 68688 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 36812 KB Output is correct
2 Correct 506 ms 37400 KB Output is correct
3 Correct 345 ms 34640 KB Output is correct
4 Correct 504 ms 22500 KB Output is correct
5 Correct 723 ms 70100 KB Output is correct
6 Correct 705 ms 70168 KB Output is correct
7 Correct 709 ms 70052 KB Output is correct
8 Correct 692 ms 70100 KB Output is correct
9 Correct 628 ms 69880 KB Output is correct
10 Correct 642 ms 69928 KB Output is correct
11 Correct 656 ms 69876 KB Output is correct
12 Correct 628 ms 69888 KB Output is correct