oj.uz

Submission #1034157

# Submission time Handle Problem Language Result Execution time Memory
1034157 2024-07-25T10:11:57 Z juicy Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 343 ms 68012 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 1e5 + 5, LG = 31;
 
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) {
	for (int i = 0; i < LG; ++i) {
		if (i + x < LG) {
			s[id][i] = s[id][i + x];
			s[id][i + x] = 0;
		} else {
			s[id][i] = 0;
		}
	}
	lz[id] += x;
}
 
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 (u <= l && r <= v) {
		app(id, 1);
		return;
	}
	psh(id);
	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 2 ms 1372 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct
7 Correct 6 ms 2396 KB Output is correct
8 Correct 5 ms 2396 KB Output is correct
9 Correct 7 ms 2396 KB Output is correct
10 Correct 6 ms 2476 KB Output is correct
11 Correct 6 ms 2368 KB Output is correct
12 Correct 7 ms 2392 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33780 KB Output is correct
2 Correct 41 ms 19540 KB Output is correct
3 Correct 66 ms 65204 KB Output is correct
4 Correct 83 ms 65620 KB Output is correct
5 Correct 81 ms 65876 KB Output is correct
6 Correct 88 ms 65872 KB Output is correct
7 Correct 82 ms 66012 KB Output is correct
8 Correct 84 ms 65872 KB Output is correct
9 Correct 80 ms 65616 KB Output is correct
10 Correct 79 ms 65620 KB Output is correct
11 Correct 80 ms 65792 KB Output is correct
12 Correct 81 ms 65616 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4956 KB Output is correct
2 Correct 70 ms 32852 KB Output is correct
3 Correct 81 ms 33104 KB Output is correct
4 Correct 177 ms 17492 KB Output is correct
5 Correct 300 ms 66176 KB Output is correct
6 Correct 305 ms 66128 KB Output is correct
7 Correct 77 ms 65108 KB Output is correct
8 Correct 332 ms 65108 KB Output is correct
9 Correct 242 ms 65364 KB Output is correct
10 Correct 223 ms 65104 KB Output is correct
11 Correct 233 ms 65104 KB Output is correct
12 Correct 233 ms 64908 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 32852 KB Output is correct
2 Correct 197 ms 34584 KB Output is correct
3 Correct 136 ms 33876 KB Output is correct
4 Correct 185 ms 18504 KB Output is correct
5 Correct 296 ms 67792 KB Output is correct
6 Correct 343 ms 68012 KB Output is correct
7 Correct 297 ms 67648 KB Output is correct
8 Correct 308 ms 67720 KB Output is correct
9 Correct 232 ms 67664 KB Output is correct
10 Correct 231 ms 67568 KB Output is correct
11 Correct 249 ms 67664 KB Output is correct
12 Correct 244 ms 67700 KB Output is correct