oj.uz

Submission #828782

# Submission time Handle Problem Language Result Execution time Memory
828782 2023-08-17T16:00:45 Z OAleksa Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 219 ms 4728 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
#define int long long
const int maxn = 1e5 + 69;
int st[4 * maxn], mx[4 * maxn], n, q, k;

void upd(int v, int tl, int tr, int x, int y) {
	if(tl == tr) 
		st[v] = mx[v] = y;
	else {
		int mid = (tl + tr) / 2;
		if(x <= mid)
			upd(v * 2, tl, mid, x, y);
		else
			upd(v * 2 + 1, mid + 1, tr, x, y);
		st[v] = st[v * 2] + st[v * 2 + 1];
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
}

void sprejamVamPoKevama(int v, int tl, int tr, int l, int r) {
	if(tl > r || tr < l)
		return;
	else if(tl >= l && tr <= r) {
		if(tl == tr)
			st[v] /= k, mx[v] /= k;
		else if(mx[v] > 0) {
			int mid = (tl + tr) / 2;
			sprejamVamPoKevama(v * 2, tl, mid, l, r);
			sprejamVamPoKevama(v * 2 + 1, mid + 1, tr, l, r);
			st[v] = st[v * 2] + st[v * 2 + 1];
			mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
		}
		return;
	}
	int mid = (tl + tr) / 2;
	sprejamVamPoKevama(v * 2, tl, mid, l, r);
	sprejamVamPoKevama(v * 2 + 1, mid + 1, tr, l, r);
	st[v] = st[v * 2] + st[v * 2 + 1];
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}

int brojimKeve(int v, int tl, int tr, int l, int r) {
	if(tl > r || tr < l)
		return 0; //no bitches
	else if(tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return brojimKeve(v * 2, tl, mid, l, r) + brojimKeve(v * 2 + 1, mid + 1, tr, l, r);
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> q >> k;
		for(int i = 1;i <= n;i++) {
			int x;
			cin >> x;
			upd(1, 1, n, i, x);
		}
		for(int i = 1;i <= q;i++) {
			int t, a, b;
			cin >> t >> a >> b;
			if(t == 1) 
				upd(1, 1, n, a, b);
			else if(t == 2 && k != 1) 
				sprejamVamPoKevama(1, 1, n, a, b);
			else 
				cout << brojimKeve(1, 1, n, a, b) << "\n";
		}
	}
   return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 600 KB Output is correct
2 Correct 13 ms 2320 KB Output is correct
3 Correct 18 ms 2388 KB Output is correct
4 Correct 50 ms 1384 KB Output is correct
5 Correct 61 ms 4436 KB Output is correct
6 Correct 60 ms 4468 KB Output is correct
7 Incorrect 57 ms 4688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2460 KB Output is correct
2 Correct 78 ms 2552 KB Output is correct
3 Correct 93 ms 2512 KB Output is correct
4 Correct 112 ms 1568 KB Output is correct
5 Correct 118 ms 4588 KB Output is correct
6 Correct 131 ms 4672 KB Output is correct
7 Correct 111 ms 4688 KB Output is correct
8 Correct 165 ms 4696 KB Output is correct
9 Correct 141 ms 4692 KB Output is correct
10 Correct 171 ms 4728 KB Output is correct
11 Correct 133 ms 4688 KB Output is correct
12 Correct 219 ms 4680 KB Output is correct