oj.uz

Submission #1034123

# Submission time Handle Problem Language Result Execution time Memory
1034123 2024-07-25T09:54:21 Z juicy Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 98 ms 64008 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 30;

int n, q, k;
int lz[4 * N];
long long s[4 * N][LG];

void pull(int id) {
	for (int j = 0; j < (k > 1 ? LG : 1); ++j) {
		s[id][j] = s[id * 2][j] + s[id * 2 + 1][j];
	}
}

void app(int id, int x) {
	x = min(x, LG);
	if (x == LG) {
		fill(s[id], s[id] + LG, 0);
	} else {
		for (int i = 0; i + x < LG; ++i) {
			s[id][i] = s[id][i + x];
			s[id][i + x] = 0;
		}
	}
}

void psh(int id) {
	assert(!lz[id]);
	if (lz[id]) {
		app(id * 2, lz[id]);
		app(id * 2 + 1, lz[id]);
		lz[id] = 0;
	}
}

void upd(int i, int x, int id = 1, int l = 1, int r = n) {
	if (l == r) {
		s[id][0] = x;
		if (k > 1) {
			for (int i = 1; i < LG; ++i) {
				x /= k;
				s[id][i] = x;
			}
		}
		return;
	}
	psh(id);
	int md = (l + r) / 2;
	if (i <= md) {
		upd(i, x, id * 2, l, md);
	} else {
		upd(i, x, id * 2 + 1, md + 1, r);
	}
	pull(id);
}

void spray(int u, int v, int id = 1, int l = 1, int r = n) {
	if (l == r) {
		app(id, 1);
		return;
	}
	int md = (l + r) / 2;
	if (u <= md) {
		spray(u, v, id * 2, l, md);
	}
	if (md < v) {
		spray(u, v, id * 2 + 1, md + 1, r);
	}
	pull(id);
}

long long qry(int u, int v, int id = 1, int l = 1, int r = n) {
	if (u <= l && r <= v) {
		return s[id][0];
	}
	psh(id);
	int md = (l + r) / 2;
	if (v <= md) {
		return qry(u, v, id * 2, l, md);
	}
	if (md < u) {
		return qry(u, v, id * 2 + 1, md + 1, r);
	}
	return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> q >> k;
	assert(k == 1);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		upd(i, x);
	}	
	while (q--) {
		int type, a, b; cin >> type >> a >> b;
		if (type == 1) {
			upd(a, b);
		} else if (type == 2) {
			if (k > 1) {
				spray(a, b, 1);
			}
		} else {
			cout << qry(a, b) << "\n";
		}
	}
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 32848 KB Output is correct
2 Correct 59 ms 19188 KB Output is correct
3 Correct 65 ms 63116 KB Output is correct
4 Correct 77 ms 63576 KB Output is correct
5 Correct 91 ms 64008 KB Output is correct
6 Correct 85 ms 63792 KB Output is correct
7 Correct 86 ms 63944 KB Output is correct
8 Correct 86 ms 63828 KB Output is correct
9 Correct 77 ms 63544 KB Output is correct
10 Correct 98 ms 63732 KB Output is correct
11 Correct 94 ms 63796 KB Output is correct
12 Correct 76 ms 63604 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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