oj.uz

Submission #342277

# Submission time Handle Problem Language Result Execution time Memory
342277 2021-01-01T17:30:07 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;
	t[v] = t[v + v] + t[v + v + 1];
	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 20 ms 492 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 16 ms 492 KB Output is correct
8 Correct 16 ms 492 KB Output is correct
9 Correct 17 ms 492 KB Output is correct
10 Correct 17 ms 492 KB Output is correct
11 Correct 16 ms 492 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 189 ms 2040 KB Output is correct
2 Correct 168 ms 1900 KB Output is correct
3 Correct 147 ms 2924 KB Output is correct
4 Correct 189 ms 3308 KB Output is correct
5 Correct 224 ms 3564 KB Output is correct
6 Correct 264 ms 3412 KB Output is correct
7 Correct 223 ms 3436 KB Output is correct
8 Correct 223 ms 3436 KB Output is correct
9 Correct 215 ms 3436 KB Output is correct
10 Correct 220 ms 3436 KB Output is correct
11 Correct 230 ms 3556 KB Output is correct
12 Correct 216 ms 3436 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 748 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 5033 ms 2188 KB Time limit exceeded
2 Halted 0 ms 0 KB -