oj.uz

Submission #342304

# Submission time Handle Problem Language Result Execution time Memory
342304 2021-01-01T19:33:09 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 6848 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];
}
int 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)
		{
			int l, r;
			cin >> l >> r;
			upd2(l, r);
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << get(l, r) << '\n';
		}
	}
}
/*           
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1132 KB Output is correct
2 Correct 43 ms 3052 KB Output is correct
3 Correct 62 ms 3180 KB Output is correct
4 Correct 178 ms 2796 KB Output is correct
5 Correct 221 ms 6848 KB Output is correct
6 Correct 221 ms 6764 KB Output is correct
7 Execution timed out 5043 ms 6396 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 4332 KB Output isn't correct
2 Halted 0 ms 0 KB -