oj.uz

Submission #342252

# Submission time Handle Problem Language Result Execution time Memory
342252 2021-01-01T16:51:00 Z Nursik Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 2028 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;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		upd(i, a[i]);
	}   
	//subtask 3
	if (k == 1)
	{
		for (int i = 1; i <= q; i++)
		{
			cin >> type;
			if (type == 1)
			{
				int pos, x;
				cin >> pos >> x;
				upd(pos, -x);
				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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 568 KB Output is correct
2 Correct 1306 ms 1132 KB Output is correct
3 Correct 2083 ms 1144 KB Output is correct
4 Correct 4073 ms 1412 KB Output is correct
5 Execution timed out 5053 ms 2028 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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