oj.uz

Submission #776373

# Submission time Handle Problem Language Result Execution time Memory
776373 2023-07-07T19:00:03 Z Hacv16 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3416 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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;
}

ll n, q, k, v[MAX], seg[4 * MAX];

void build(int p, int l, int r){
	if(l == r){
		seg[p] = 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 || seg[p] == 0) return 0;
	if(a <= l && r <= b) return seg[p];

	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 > r || i < l) return;
	if(l == r){
		seg[p] = x;	
		return;
	}

	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	update(i, x, e, l, m); 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] == 0 || a > r || b < l) return;
	if(l == r){ seg[p] /= 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();

		if(op == 1){
			ll i = get(), x = get();
			update(i, x, 1, 1, n);

		}else if(op == 2){
			ll l = get(), r = get();
			spray(l, r, 1, 1, n);

		}else{
			ll l = get(), r = get();
			cout << query(l, r, 1, 1, n) << '\n';
		}
	}

	exit(0);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3685 ms 2128 KB Output is correct
2 Correct 2366 ms 1880 KB Output is correct
3 Correct 3796 ms 3348 KB Output is correct
4 Execution timed out 5051 ms 3416 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 6 ms 1620 KB Output is correct
4 Correct 16 ms 1032 KB Output is correct
5 Correct 20 ms 3160 KB Output is correct
6 Correct 20 ms 3196 KB Output is correct
7 Execution timed out 5060 ms 3356 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1860 KB Output is correct
2 Correct 39 ms 1924 KB Output is correct
3 Correct 55 ms 1844 KB Output is correct
4 Correct 51 ms 1332 KB Output is correct
5 Correct 66 ms 3396 KB Output is correct
6 Correct 65 ms 3380 KB Output is correct
7 Correct 53 ms 3272 KB Output is correct
8 Correct 80 ms 3388 KB Output is correct
9 Correct 79 ms 3392 KB Output is correct
10 Correct 81 ms 3392 KB Output is correct
11 Correct 57 ms 3392 KB Output is correct
12 Correct 107 ms 3392 KB Output is correct