oj.uz

Submission #342305

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5082 ms 3172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 620 KB Output is correct
2 Correct 43 ms 2796 KB Output is correct
3 Correct 59 ms 2796 KB Output is correct
4 Correct 176 ms 1652 KB Output is correct
5 Correct 224 ms 5356 KB Output is correct
6 Correct 217 ms 5356 KB Output is correct
7 Execution timed out 5049 ms 5484 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 3052 KB Output is correct
2 Correct 238 ms 4716 KB Output is correct
3 Correct 218 ms 4076 KB Output is correct
4 Correct 282 ms 3564 KB Output is correct
5 Correct 339 ms 8060 KB Output is correct
6 Correct 369 ms 8092 KB Output is correct
7 Correct 334 ms 7916 KB Output is correct
8 Correct 410 ms 8172 KB Output is correct
9 Correct 390 ms 7916 KB Output is correct
10 Correct 420 ms 8172 KB Output is correct
11 Correct 351 ms 7788 KB Output is correct
12 Correct 509 ms 7916 KB Output is correct