oj.uz

Submission #156568

# Submission time Handle Problem Language Result Execution time Memory
156568 2019-10-06T14:16:30 Z Saboon Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 444 ms 7436 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

ll sum[4 * maxn], mxm[4 * maxn];

ll get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return sum[id];
	int mid = (L + R) >> 1;
	return get(2 * id + 0, L, mid, l, r) + get(2 * id + 1, mid, R, l, r);
}

void change(int id, int L, int R, int l, int r, int k){
	if (r <= L or R <= l or mxm[id] == 0)
		return;
	if (L + 1 == R){
		int x = mxm[id] / k;
		sum[id] = mxm[id] = x;
		return;
	}
	int mid = (L + R) >> 1;
	change(2 * id + 0, L, mid, l, r, k);
	change(2 * id + 1, mid, R, l, r, k);
	sum[id] = sum[2 * id + 0] + sum[2 * id + 1];
	mxm[id] = max(mxm[2 * id + 0], mxm[2 * id + 1]);
}

void apply(int id, int L, int R, int idx, int val){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		sum[id] = mxm[id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	apply(2 * id + 0, L, mid, idx, val);
	apply(2 * id + 1, mid, R, idx, val);
	sum[id] = sum[2 * id + 0] + sum[2 * id + 1];
	mxm[id] = max(mxm[2 * id + 0], mxm[2 * id + 1]);
}

int main(){
	ios_base::sync_with_stdio (false);
	int n, q, k;
	cin >> n >> q >> k;
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		apply(1, 0, n, i, a);
	}
	for (int i = 0; i < q; i++){
		int type, a, b;
		cin >> type >> a >> b;
		if (type == 1){
			a --;
			apply(1, 0, n, a, b);
		}
		else if (type == 2){
			a --;
			if (k > 1)
				change(1, 0, n, a, b, k);
		}
		else{
			a --;
			cout << get(1, 0, n, a, b) << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 9 ms 504 KB Output is correct
5 Correct 10 ms 504 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 10 ms 636 KB Output is correct
10 Correct 9 ms 632 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 10 ms 760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4768 KB Output is correct
2 Correct 145 ms 4496 KB Output is correct
3 Correct 123 ms 6392 KB Output is correct
4 Correct 158 ms 6904 KB Output is correct
5 Correct 190 ms 7416 KB Output is correct
6 Correct 190 ms 7416 KB Output is correct
7 Correct 198 ms 7416 KB Output is correct
8 Correct 192 ms 7436 KB Output is correct
9 Correct 185 ms 7288 KB Output is correct
10 Correct 186 ms 7256 KB Output is correct
11 Correct 186 ms 7412 KB Output is correct
12 Correct 184 ms 7272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1016 KB Output is correct
2 Correct 38 ms 2680 KB Output is correct
3 Correct 53 ms 2888 KB Output is correct
4 Correct 151 ms 2680 KB Output is correct
5 Correct 189 ms 5992 KB Output is correct
6 Correct 188 ms 6008 KB Output is correct
7 Correct 180 ms 6096 KB Output is correct
8 Correct 189 ms 5940 KB Output is correct
9 Correct 182 ms 5780 KB Output is correct
10 Correct 181 ms 5792 KB Output is correct
11 Correct 181 ms 5912 KB Output is correct
12 Correct 182 ms 5860 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 4236 KB Output is correct
2 Correct 211 ms 4312 KB Output is correct
3 Correct 201 ms 3656 KB Output is correct
4 Correct 240 ms 3340 KB Output is correct
5 Correct 286 ms 7208 KB Output is correct
6 Correct 311 ms 7340 KB Output is correct
7 Correct 277 ms 7188 KB Output is correct
8 Correct 360 ms 7288 KB Output is correct
9 Correct 322 ms 7192 KB Output is correct
10 Correct 358 ms 7052 KB Output is correct
11 Correct 297 ms 7176 KB Output is correct
12 Correct 444 ms 7160 KB Output is correct