oj.uz

Submission #1034095

# Submission time Handle Problem Language Result Execution time Memory
1034095 2024-07-25T09:46:00 Z juicy Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 64872 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 < LG; ++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) {
	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) {
		for (int i = 0; i < LG; ++i) {
			s[id][i] = x;
			x /= k;
		}
		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;
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 1368 KB Output is correct
4 Correct 14 ms 1372 KB Output is correct
5 Correct 30 ms 2392 KB Output is correct
6 Correct 31 ms 2396 KB Output is correct
7 Correct 29 ms 2468 KB Output is correct
8 Correct 31 ms 2396 KB Output is correct
9 Correct 30 ms 2468 KB Output is correct
10 Correct 31 ms 2396 KB Output is correct
11 Correct 29 ms 2396 KB Output is correct
12 Correct 31 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 33364 KB Output is correct
2 Correct 63 ms 19792 KB Output is correct
3 Correct 98 ms 63772 KB Output is correct
4 Correct 115 ms 64340 KB Output is correct
5 Correct 168 ms 64852 KB Output is correct
6 Correct 132 ms 64836 KB Output is correct
7 Correct 131 ms 64848 KB Output is correct
8 Correct 134 ms 64872 KB Output is correct
9 Correct 130 ms 64596 KB Output is correct
10 Correct 138 ms 64776 KB Output is correct
11 Correct 129 ms 64596 KB Output is correct
12 Correct 120 ms 64632 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 4568 KB Output is correct
2 Correct 2319 ms 31516 KB Output is correct
3 Correct 3487 ms 31604 KB Output is correct
4 Execution timed out 5053 ms 16976 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 32336 KB Time limit exceeded
2 Halted 0 ms 0 KB -