oj.uz

Submission #342281

# Submission time Handle Problem Language Result Execution time Memory
342281 2021-01-01T17:37:25 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 3692 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);
	t[v] = t[v + v] + t[v + v + 1];
}
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 11 ms 492 KB Output is correct
5 Correct 16 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 18 ms 620 KB Output is correct
10 Correct 23 ms 620 KB Output is correct
11 Correct 18 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 187 ms 2156 KB Output is correct
2 Correct 162 ms 1772 KB Output is correct
3 Correct 147 ms 2924 KB Output is correct
4 Correct 196 ms 3328 KB Output is correct
5 Correct 226 ms 3436 KB Output is correct
6 Correct 232 ms 3436 KB Output is correct
7 Correct 225 ms 3436 KB Output is correct
8 Correct 221 ms 3436 KB Output is correct
9 Correct 219 ms 3436 KB Output is correct
10 Correct 219 ms 3436 KB Output is correct
11 Correct 226 ms 3564 KB Output is correct
12 Correct 219 ms 3692 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 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 5095 ms 2136 KB Time limit exceeded
2 Halted 0 ms 0 KB -