oj.uz

Submission #828779

# Submission time Handle Problem Language Result Execution time Memory
828779 2023-08-17T15:58:18 Z OAleksa Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 196 ms 4736 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(mx[v] > 0) {
			if(tl == tr)
				st[v] /= k, mx[v] /= k;
			else {
				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 1 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 51 ms 3220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 596 KB Output is correct
2 Correct 13 ms 2396 KB Output is correct
3 Correct 17 ms 2392 KB Output is correct
4 Correct 42 ms 1384 KB Output is correct
5 Correct 61 ms 4476 KB Output is correct
6 Correct 61 ms 4468 KB Output is correct
7 Incorrect 56 ms 4684 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 69 ms 2512 KB Output is correct
2 Correct 76 ms 2652 KB Output is correct
3 Correct 92 ms 2512 KB Output is correct
4 Correct 93 ms 1572 KB Output is correct
5 Correct 119 ms 4676 KB Output is correct
6 Correct 146 ms 4600 KB Output is correct
7 Correct 122 ms 4676 KB Output is correct
8 Correct 151 ms 4704 KB Output is correct
9 Correct 131 ms 4696 KB Output is correct
10 Correct 150 ms 4736 KB Output is correct
11 Correct 113 ms 4676 KB Output is correct
12 Correct 196 ms 4676 KB Output is correct