oj.uz

Submission #342264

# Submission time Handle Problem Language Result Execution time Memory
342264 2021-01-01T17:00:36 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 2540 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 main()
{
	data();     
	cin >> n >> q >> k;
	bool check = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(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;
				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 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 3 ms 364 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 16 ms 364 KB Output is correct
6 Correct 17 ms 364 KB Output is correct
7 Correct 17 ms 364 KB Output is correct
8 Correct 16 ms 364 KB Output is correct
9 Correct 17 ms 364 KB Output is correct
10 Correct 17 ms 512 KB Output is correct
11 Correct 21 ms 364 KB Output is correct
12 Correct 18 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1644 KB Output is correct
2 Correct 162 ms 1260 KB Output is correct
3 Correct 138 ms 2028 KB Output is correct
4 Correct 173 ms 2412 KB Output is correct
5 Correct 208 ms 2540 KB Output is correct
6 Correct 214 ms 2412 KB Output is correct
7 Correct 227 ms 2412 KB Output is correct
8 Correct 238 ms 2412 KB Output is correct
9 Correct 202 ms 2412 KB Output is correct
10 Correct 201 ms 2412 KB Output is correct
11 Correct 214 ms 2412 KB Output is correct
12 Correct 221 ms 2436 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 512 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 5022 ms 1796 KB Time limit exceeded
2 Halted 0 ms 0 KB -