oj.uz

Submission #412413

# Submission time Handle Problem Language Result Execution time Memory
412413 2021-05-26T20:26:09 Z aryan12 Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 3156 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;
int seg[N * 4];
int a[N], k;

void Build(int l, int r, int pos) {
	if(l == r) {
		seg[pos] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Update(int l, int r, int pos, int qidx, int qval) {
	if(l == r) {
		seg[pos] = qval;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qidx) {
		Update(l, mid, pos * 2, qidx, qval);
	}
	else {
		Update(mid + 1, r, pos * 2 + 1, qidx, qval);
	}
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Spray(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return;
	if(l == r) {
		seg[pos] /= k;
		return;
	}
	int mid = (l + r) >> 1;
	Spray(l, mid, pos * 2, ql, qr);
	Spray(mid + 1, r, pos * 2 + 1, ql, qr);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

int Query(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return 0;
	if(ql <= l && r <= qr) {
		return seg[pos];
	}
	int mid = (l + r) >> 1;
	return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr);
}

void Solve() {
	int n, q;
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		assert(a[i] <= 1);
	}
	Build(1, n, 1);
	for(int i = 1; i <= q; i++) {
		int command;
		cin >> command;
		if(command == 1) {
			int idx, val;
			cin >> idx >> val;
			assert(val <= 1);
			Update(1, n, 1, idx, val);
		}
		else if(command == 2) {
			int ql, qr;
			cin >> ql >> qr;
			if(k != 1) {
				Spray(1, n, 1, ql, qr);
			}
		}
		else {
			int ql, qr;
			cin >> ql >> qr;
			cout << Query(1, n, 1, ql, qr) << "\n";
		}
	}
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 636 KB Output is correct
2 Correct 716 ms 1684 KB Output is correct
3 Correct 1131 ms 1860 KB Output is correct
4 Correct 2489 ms 1172 KB Output is correct
5 Execution timed out 5050 ms 3156 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -