oj.uz

Submission #828785

# Submission time Handle Problem Language Result Execution time Memory
828785 2023-08-17T16:04:37 Z OAleksa Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 196 ms 7116 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 if(t == 3)
				cout << brojimKeve(1, 1, n, a, b) << "\n";
		}
	}
   return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2764 KB Output is correct
2 Correct 42 ms 4408 KB Output is correct
3 Correct 36 ms 6304 KB Output is correct
4 Correct 46 ms 6808 KB Output is correct
5 Correct 53 ms 6988 KB Output is correct
6 Correct 52 ms 6972 KB Output is correct
7 Correct 51 ms 7028 KB Output is correct
8 Correct 53 ms 7080 KB Output is correct
9 Correct 55 ms 7116 KB Output is correct
10 Correct 48 ms 7068 KB Output is correct
11 Correct 48 ms 6988 KB Output is correct
12 Correct 48 ms 7080 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Correct 17 ms 2400 KB Output is correct
3 Correct 18 ms 2332 KB Output is correct
4 Correct 44 ms 1412 KB Output is correct
5 Correct 60 ms 4468 KB Output is correct
6 Correct 59 ms 4448 KB Output is correct
7 Correct 46 ms 4556 KB Output is correct
8 Correct 61 ms 5904 KB Output is correct
9 Correct 56 ms 5720 KB Output is correct
10 Correct 56 ms 5700 KB Output is correct
11 Correct 74 ms 5708 KB Output is correct
12 Correct 62 ms 5732 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2520 KB Output is correct
2 Correct 76 ms 2584 KB Output is correct
3 Correct 85 ms 2508 KB Output is correct
4 Correct 93 ms 1604 KB Output is correct
5 Correct 111 ms 4676 KB Output is correct
6 Correct 139 ms 4628 KB Output is correct
7 Correct 108 ms 4616 KB Output is correct
8 Correct 150 ms 4652 KB Output is correct
9 Correct 133 ms 4696 KB Output is correct
10 Correct 155 ms 4732 KB Output is correct
11 Correct 117 ms 4652 KB Output is correct
12 Correct 196 ms 4732 KB Output is correct