oj.uz

Submission #342306

# Submission time Handle Problem Language Result Execution time Memory
342306 2021-01-01T19:35:13 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 507 ms 6764 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();     
	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 5 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 364 KB Output is correct
5 Correct 10 ms 492 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 9 ms 492 KB Output is correct
8 Correct 9 ms 492 KB Output is correct
9 Correct 10 ms 492 KB Output is correct
10 Correct 9 ms 492 KB Output is correct
11 Correct 9 ms 492 KB Output is correct
12 Correct 9 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 3692 KB Output is correct
2 Correct 178 ms 3948 KB Output is correct
3 Correct 161 ms 6124 KB Output is correct
4 Correct 202 ms 6380 KB Output is correct
5 Correct 243 ms 6508 KB Output is correct
6 Correct 240 ms 6508 KB Output is correct
7 Correct 262 ms 6508 KB Output is correct
8 Correct 242 ms 6508 KB Output is correct
9 Correct 231 ms 6636 KB Output is correct
10 Correct 235 ms 6764 KB Output is correct
11 Correct 233 ms 6508 KB Output is correct
12 Correct 233 ms 6508 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 620 KB Output is correct
2 Correct 42 ms 2796 KB Output is correct
3 Correct 60 ms 2796 KB Output is correct
4 Correct 180 ms 1644 KB Output is correct
5 Correct 220 ms 5356 KB Output is correct
6 Correct 219 ms 5228 KB Output is correct
7 Correct 211 ms 5996 KB Output is correct
8 Correct 219 ms 6764 KB Output is correct
9 Correct 214 ms 6704 KB Output is correct
10 Correct 208 ms 6636 KB Output is correct
11 Correct 215 ms 6640 KB Output is correct
12 Correct 206 ms 6636 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 3052 KB Output is correct
2 Correct 241 ms 3052 KB Output is correct
3 Correct 239 ms 2924 KB Output is correct
4 Correct 277 ms 2156 KB Output is correct
5 Correct 343 ms 5464 KB Output is correct
6 Correct 370 ms 5612 KB Output is correct
7 Correct 334 ms 5504 KB Output is correct
8 Correct 464 ms 5676 KB Output is correct
9 Correct 399 ms 5708 KB Output is correct
10 Correct 420 ms 5868 KB Output is correct
11 Correct 351 ms 5612 KB Output is correct
12 Correct 507 ms 5624 KB Output is correct