oj.uz

Submission #754840

# Submission time Handle Problem Language Result Execution time Memory
754840 2023-06-08T17:28:20 Z raysh07 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 224 ms 8236 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF (int)(1e9)
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int n, q, k;
pair <int, int> seg[4 * N]; //{sum, mn}
int a[N];

void Build(int l, int r, int pos){
	if (l == r){
		seg[pos] = make_pair(a[l], a[l]);
		return;
	}

	int mid = (l + r)/2;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

void upd(int l, int r, int pos, int qp, int v){
	if (l == r){
		seg[pos] = make_pair(v, v);
		return;
	}

	int mid = (l + r)/2;
	if (qp <= mid) upd(l, mid, pos*2, qp, v);
	else upd(mid + 1, r, pos*2 + 1, qp, v);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

void divide(int l, int r, int pos, int ql, int qr){
	if (seg[pos].f == 0 || l > qr || r < ql) return;

	if (l == r){
		seg[pos].f /= k;
		seg[pos].s = seg[pos].f;
		return;
	}

	int mid = (l + r)/2;
	divide(l, mid, pos*2, ql, qr);
	divide(mid + 1, r, pos*2 + 1, ql, qr);

	seg[pos].f = seg[pos * 2].f + seg[pos * 2 + 1].f;
	seg[pos].s = min(seg[pos * 2].s, seg[pos * 2 + 1].s);
}

int query(int l, int r, int pos, int ql, int qr){
	if (l >= ql && r <= qr) return seg[pos].f;
	else if (l > qr || r < ql) return 0;

	int mid = (l + r)/2;
	return query(l, mid, pos*2, ql, qr) + query(mid + 1, r, pos*2 + 1, ql, qr);
}

void Solve(){
	cin >> n >> q >> k;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}

	Build(1, n, 1);

	while (q--){
		int t; cin >> t;

		int x, y; cin >> x >> y;

		if (t == 1){
			upd(1, n, 1, x, y);
		} else if (t == 2){
			if (k != 1){
				divide(1, n, 1, x, y);
			}
		} else {
			cout << query(1, n, 1, x, y) << "\n";
		}
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1; 
	//cin >> t;
	
	while (t--) Solve();
	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 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 4 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 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 532 KB Output is correct
12 Correct 3 ms 528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5108 KB Output is correct
2 Correct 37 ms 4608 KB Output is correct
3 Correct 36 ms 6912 KB Output is correct
4 Correct 45 ms 7692 KB Output is correct
5 Correct 55 ms 8236 KB Output is correct
6 Correct 53 ms 8052 KB Output is correct
7 Correct 53 ms 8048 KB Output is correct
8 Correct 58 ms 8032 KB Output is correct
9 Correct 50 ms 7936 KB Output is correct
10 Correct 50 ms 7884 KB Output is correct
11 Correct 51 ms 8008 KB Output is correct
12 Correct 55 ms 7980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1108 KB Output is correct
2 Correct 11 ms 3032 KB Output is correct
3 Correct 15 ms 3028 KB Output is correct
4 Correct 44 ms 2704 KB Output is correct
5 Correct 51 ms 6632 KB Output is correct
6 Correct 53 ms 6620 KB Output is correct
7 Correct 55 ms 6772 KB Output is correct
8 Correct 55 ms 6652 KB Output is correct
9 Correct 48 ms 6532 KB Output is correct
10 Correct 50 ms 6572 KB Output is correct
11 Correct 67 ms 6476 KB Output is correct
12 Correct 48 ms 6472 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4380 KB Output is correct
2 Correct 85 ms 4652 KB Output is correct
3 Correct 97 ms 4032 KB Output is correct
4 Correct 102 ms 3452 KB Output is correct
5 Correct 124 ms 7872 KB Output is correct
6 Correct 140 ms 7868 KB Output is correct
7 Correct 118 ms 7872 KB Output is correct
8 Correct 158 ms 7836 KB Output is correct
9 Correct 145 ms 7796 KB Output is correct
10 Correct 165 ms 7760 KB Output is correct
11 Correct 124 ms 7772 KB Output is correct
12 Correct 224 ms 7828 KB Output is correct