oj.uz

Submission #1034100

# Submission time Handle Problem Language Result Execution time Memory
1034100 2024-07-25T09:48:29 Z juicy Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 62480 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) {
	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;
	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 5 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 1368 KB Output is correct
4 Correct 18 ms 1444 KB Output is correct
5 Correct 38 ms 2396 KB Output is correct
6 Correct 40 ms 2396 KB Output is correct
7 Correct 38 ms 2136 KB Output is correct
8 Correct 37 ms 2396 KB Output is correct
9 Correct 49 ms 2648 KB Output is correct
10 Correct 40 ms 2396 KB Output is correct
11 Correct 46 ms 2396 KB Output is correct
12 Correct 41 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31548 KB Output is correct
2 Correct 42 ms 18116 KB Output is correct
3 Correct 71 ms 62088 KB Output is correct
4 Correct 72 ms 62284 KB Output is correct
5 Correct 82 ms 62288 KB Output is correct
6 Correct 79 ms 62480 KB Output is correct
7 Correct 77 ms 62288 KB Output is correct
8 Correct 86 ms 62340 KB Output is correct
9 Correct 77 ms 62288 KB Output is correct
10 Correct 74 ms 62332 KB Output is correct
11 Correct 70 ms 62288 KB Output is correct
12 Correct 75 ms 62284 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 4316 KB Output is correct
2 Correct 2911 ms 31236 KB Output is correct
3 Correct 4996 ms 31236 KB Output is correct
4 Execution timed out 5054 ms 15708 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 5045 ms 31264 KB Time limit exceeded
2 Halted 0 ms 0 KB -