oj.uz

Submission #342275

# Submission time Handle Problem Language Result Execution time Memory
342275 2021-01-01T17:28:13 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 3564 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;
ll a[N];
ll f[N];
int type;
void upd(int pos, ll val)
{
	for (int i = pos; i <= n; i |= (i + 1))
	{
		f[i] += val;
	}
}
ll get(int pos)
{
	ll res = 0;
	for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
	{
		res += f[i];
	}
	return res;
}
int t[N * 4], m[N * 4];
void upd2(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
	if (tl == tr)
	{
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		upd2(pos, val, v * 2, tl, tm);
	else
		upd2(pos, val, v * 2 + 1, tm + 1, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v)
{
	if (m[v])
	{
		t[v * 2] = t[v];
		t[v * 2 + 1] = t[v];
		m[v * 2] = m[v];
		m[v * 2 + 1] = m[v];
		m[v] = 0;
	}
}
int get3(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v);
	if (l <= tl && tr <= r)
		return t[v];
	if (l > tl || r < tl)
		return 0;
	int tm = (tl + tr) / 2;
	return get3(l, r, v * 2, tl, tm) + get3(l, r, v * 2 + 1, tm + 1, tr);
}
void get2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	push(v);
	if (l <= tl && tr <= r)
	{
		m[v] = 1;
		t[v] = 0;
		push(v);
		return;
	}
	if (l > tr || r < tl)
		return;
	int tm = (tl + tr) / 2;
	get2(l, r, v * 2, tl, tm);
	get2(l, r, v * 2 + 1, tm + 1, tr);
}
int main()
{
	data();     
	cin >> n >> q >> k;
	int check = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
		upd2(i, a[i]);
		check = (check | (a[i] > 1));
	}   
	//subtask 3
	if (check == 0)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				a[pos] = x;
				upd2(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
				if (k > 1)
				{
					get2(l, r);
				}
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get3(l, r) << '\n';
			}
		}
		return 0;	
	}
	//subtask 2
	if (k == 1)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				upd(pos, -a[pos]);
				a[pos] = x;
				upd(pos, x);
			}
			else if (type == 2)
			{
				int l, r;
				cin >> l >> r;
			}
			else
			{
				int l, r;
				cin >> l >> r;
				cout << get(r) - get(l - 1) << '\n';
			}
		}
		return 0;
	}
	//subtask 1
	for (int i = 1; i <= q; i++)
	{
		cin >> type;
		if (type == 1)
		{
			int pos, x;
			cin >> pos >> x;
			upd(pos, -a[pos]);
			a[pos] = x;
			upd(pos, x);
		}
		else if (type == 2)
		{
			int l, r;
			cin >> l >> r;
			for (int j = l; j <= r; j++)
			{
				upd(j, -a[j]);
				upd(j, a[j] / k);
				a[j] /= k;
			}
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << get(r) - get(l - 1) << '\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 10 ms 364 KB Output is correct
5 Correct 18 ms 492 KB Output is correct
6 Correct 17 ms 620 KB Output is correct
7 Correct 16 ms 492 KB Output is correct
8 Correct 17 ms 492 KB Output is correct
9 Correct 17 ms 640 KB Output is correct
10 Correct 18 ms 492 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 17 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 2156 KB Output is correct
2 Correct 161 ms 1812 KB Output is correct
3 Correct 146 ms 2908 KB Output is correct
4 Correct 187 ms 3308 KB Output is correct
5 Correct 223 ms 3436 KB Output is correct
6 Correct 222 ms 3436 KB Output is correct
7 Correct 224 ms 3564 KB Output is correct
8 Correct 220 ms 3564 KB Output is correct
9 Correct 216 ms 3436 KB Output is correct
10 Correct 213 ms 3436 KB Output is correct
11 Correct 215 ms 3436 KB Output is correct
12 Correct 214 ms 3436 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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