oj.uz

Submission #776397

# Submission time Handle Problem Language Result Execution time Memory
776397 2023-07-07T20:06:46 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++11
80 / 100
 5000 ms 13992 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 2e5 + 10;
 
inline ll get(void) {
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    ll ret = 0;
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
    return ret;
}
 
struct Node{
	ll sum, mx;
	Node(ll a = 0, ll b = 0) : sum(a), mx(b) { }

	Node operator + (Node other){
		return Node(sum + other.sum, max(mx, other.mx));
	}

} seg[4 * MAX];

ll n, q, k, v[4 * MAX];
 
void build(int p, int l, int r){
	if(l == r){
		seg[p] = Node(v[l], v[l]);
		return;
	}
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	build(e, l, m); build(d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
}
 
ll query(int a, int b, int p, int l, int r){
	if(a > r || b < l) return 0;
	if(a <= l && r <= b) return seg[p].sum;
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	return query(a, b, e, l, m) + query(a, b, d, m + 1, r);
}
 
void update(int i, ll x, int p, int l, int r){
	if(i < l || i > r) return;
	if(l == r){
		seg[p] = Node(x, x);
		return;
	}
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	if(i <= m) update(i, x, e, l, m);
	else update(i, x, d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
}
 
void spray(int a, int b, int p, int l, int r){
	if(seg[p].mx == 0 || a > r || b < l) return;
	if(l == r){ seg[p].sum /= k; seg[p].mx /= k; return; }
 
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	spray(a, b, e, l, m); spray(a, b, d, m + 1, r);
 
	seg[p] = seg[e] + seg[d];
}
 
int32_t main(void){
	n = get(); q = get(); k = get();
 
	for(int i = 1; i <= n; i++) v[i] = get();
 
	build(1, 1, n);
 
	while(q--){
		int op = get(), a = get(), b = get();
		if(op == 1) update(a, b, 1, 1, n);
		else if(op == 2) spray(a, b, 1, 1, n);
 		else cout << query(a, b, 1, 1, n) << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12816 KB Output is correct
2 Correct 8 ms 12728 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 8 ms 12860 KB Output is correct
6 Correct 7 ms 12872 KB Output is correct
7 Correct 7 ms 12756 KB Output is correct
8 Correct 10 ms 12756 KB Output is correct
9 Correct 9 ms 12836 KB Output is correct
10 Correct 7 ms 12756 KB Output is correct
11 Correct 7 ms 12756 KB Output is correct
12 Correct 9 ms 12756 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12884 KB Output is correct
2 Correct 10 ms 13140 KB Output is correct
3 Correct 13 ms 13140 KB Output is correct
4 Correct 30 ms 13060 KB Output is correct
5 Correct 33 ms 13652 KB Output is correct
6 Correct 33 ms 13652 KB Output is correct
7 Execution timed out 5037 ms 13768 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 13360 KB Output is correct
2 Correct 67 ms 13364 KB Output is correct
3 Correct 85 ms 13236 KB Output is correct
4 Correct 84 ms 13356 KB Output is correct
5 Correct 97 ms 13848 KB Output is correct
6 Correct 113 ms 13860 KB Output is correct
7 Correct 89 ms 13876 KB Output is correct
8 Correct 138 ms 13876 KB Output is correct
9 Correct 119 ms 13872 KB Output is correct
10 Correct 139 ms 13992 KB Output is correct
11 Correct 97 ms 13816 KB Output is correct
12 Correct 196 ms 13872 KB Output is correct