oj.uz

Submission #828771

# Submission time Handle Problem Language Result Execution time Memory
828771 2023-08-17T15:49:49 Z OAleksa Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 7704 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) 
				sprejamVamPoKevama(1, 1, n, a, b);
			else 
				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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 596 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 536 KB Output is correct
9 Correct 3 ms 564 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 568 KB Output is correct
12 Correct 3 ms 468 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1108 KB Output is correct
2 Correct 10 ms 2968 KB Output is correct
3 Correct 14 ms 3156 KB Output is correct
4 Correct 50 ms 2700 KB Output is correct
5 Correct 64 ms 6632 KB Output is correct
6 Correct 51 ms 6620 KB Output is correct
7 Execution timed out 5049 ms 6376 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4472 KB Output is correct
2 Correct 81 ms 4692 KB Output is correct
3 Correct 86 ms 4036 KB Output is correct
4 Correct 112 ms 3484 KB Output is correct
5 Correct 131 ms 7652 KB Output is correct
6 Correct 126 ms 7664 KB Output is correct
7 Correct 103 ms 7584 KB Output is correct
8 Correct 152 ms 7600 KB Output is correct
9 Correct 153 ms 7628 KB Output is correct
10 Correct 158 ms 7704 KB Output is correct
11 Correct 110 ms 7572 KB Output is correct
12 Correct 192 ms 7672 KB Output is correct