oj.uz

Submission #776396

# Submission time Handle Problem Language Result Execution time Memory
776396 2023-07-07T19:59:59 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 8168 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 1e5 + 15;
 
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[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(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 4 ms 6612 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 6 ms 6740 KB Output is correct
6 Correct 5 ms 6612 KB Output is correct
7 Correct 5 ms 6584 KB Output is correct
8 Correct 5 ms 6660 KB Output is correct
9 Correct 6 ms 6668 KB Output is correct
10 Correct 6 ms 6644 KB Output is correct
11 Correct 5 ms 6648 KB Output is correct
12 Correct 5 ms 6612 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6996 KB Output is correct
2 Correct 8 ms 7124 KB Output is correct
3 Correct 10 ms 7288 KB Output is correct
4 Correct 32 ms 7372 KB Output is correct
5 Correct 32 ms 7872 KB Output is correct
6 Correct 31 ms 7872 KB Output is correct
7 Execution timed out 5073 ms 7936 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7508 KB Output is correct
2 Correct 64 ms 7616 KB Output is correct
3 Correct 83 ms 7444 KB Output is correct
4 Correct 81 ms 7480 KB Output is correct
5 Correct 93 ms 8040 KB Output is correct
6 Correct 108 ms 8104 KB Output is correct
7 Correct 89 ms 8096 KB Output is correct
8 Correct 141 ms 8052 KB Output is correct
9 Correct 115 ms 8120 KB Output is correct
10 Correct 136 ms 8160 KB Output is correct
11 Correct 96 ms 8096 KB Output is correct
12 Correct 195 ms 8168 KB Output is correct