oj.uz

Submission #342307

# Submission time Handle Problem Language Result Execution time Memory
342307 2021-01-01T19:36:01 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 366 ms 5868 KB 
#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
}
void speed_force() {
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
} 
                     
int n, q, k, type, l, r;
ll a[N], t[N * 4], t2[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
	{
		t[v] = val;
		t2[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		upd(pos, val, v * 2, tl, tm);
	else
		upd(pos, val, v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
	t2[v] = t2[v + v] + t2[v + v + 1];
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if (l <= tl && tr <= r)
		return t2[v];
	if (l > tr || r < tl)
		return 0;
	int tm = (tl + tr) / 2;
	return get(l, r, v * 2, tl, tm) + get(l, r, v * 2 + 1, tm + 1, tr);
}
void upd2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	if (l > tr || r < tl || t[v] == 0)
		return;
	if (tl == tr)
	{
		t[v] = t[v] / k, t2[v] = t2[v] / k;
		return;
	}
	int tm = (tl + tr) / 2;
	upd2(l, r, v * 2, tl, tm);
	upd2(l, r, v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
	t2[v] = t2[v + v] + t2[v + v + 1];
}
int main()
{
	data();
	speed_force();     
	cin >> n >> q >> k;  
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
	}
	for (int i = 1; i <= q; i++)
	{
		cin >> type;
		if (type == 1)
		{
			int pos, x;
			cin >> pos >> x;
			upd(pos, x);
		}
		else if (type == 2)
		{
			cin >> l >> r;
			if (k > 1)
			{
				upd2(l, r);
			}
		}
		else
		{
			cin >> l >> r;
			cout << get(l, r) << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3308 KB Output is correct
2 Correct 56 ms 3052 KB Output is correct
3 Correct 55 ms 5356 KB Output is correct
4 Correct 72 ms 5612 KB Output is correct
5 Correct 86 ms 5740 KB Output is correct
6 Correct 83 ms 5740 KB Output is correct
7 Correct 82 ms 5740 KB Output is correct
8 Correct 83 ms 5868 KB Output is correct
9 Correct 88 ms 5740 KB Output is correct
10 Correct 80 ms 5740 KB Output is correct
11 Correct 84 ms 5740 KB Output is correct
12 Correct 77 ms 5740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 20 ms 2796 KB Output is correct
3 Correct 27 ms 2924 KB Output is correct
4 Correct 64 ms 1644 KB Output is correct
5 Correct 91 ms 5356 KB Output is correct
6 Correct 85 ms 5356 KB Output is correct
7 Correct 81 ms 5484 KB Output is correct
8 Correct 85 ms 5316 KB Output is correct
9 Correct 78 ms 5356 KB Output is correct
10 Correct 80 ms 5356 KB Output is correct
11 Correct 79 ms 5356 KB Output is correct
12 Correct 85 ms 5356 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3052 KB Output is correct
2 Correct 119 ms 3052 KB Output is correct
3 Correct 146 ms 2924 KB Output is correct
4 Correct 146 ms 1900 KB Output is correct
5 Correct 178 ms 5484 KB Output is correct
6 Correct 203 ms 5484 KB Output is correct
7 Correct 173 ms 5740 KB Output is correct
8 Correct 259 ms 5612 KB Output is correct
9 Correct 228 ms 5612 KB Output is correct
10 Correct 264 ms 5612 KB Output is correct
11 Correct 192 ms 5612 KB Output is correct
12 Correct 366 ms 5740 KB Output is correct