oj.uz

Submission #828774

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

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

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++)
			cin >> a[i];
		build(1, 1, n);
		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 48 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 660 KB Output is correct
2 Correct 10 ms 2744 KB Output is correct
3 Correct 20 ms 2748 KB Output is correct
4 Correct 42 ms 1596 KB Output is correct
5 Correct 53 ms 5224 KB Output is correct
6 Correct 52 ms 5260 KB Output is correct
7 Incorrect 49 ms 5752 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 67 ms 2900 KB Output is correct
2 Correct 78 ms 2892 KB Output is correct
3 Correct 85 ms 2880 KB Output is correct
4 Correct 91 ms 1888 KB Output is correct
5 Correct 113 ms 5392 KB Output is correct
6 Correct 123 ms 5432 KB Output is correct
7 Correct 102 ms 5420 KB Output is correct
8 Correct 142 ms 5440 KB Output is correct
9 Correct 128 ms 5456 KB Output is correct
10 Correct 141 ms 5468 KB Output is correct
11 Correct 124 ms 5452 KB Output is correct
12 Correct 190 ms 5536 KB Output is correct