oj.uz

Submission #88130

# Submission time Handle Problem Language Result Execution time Memory
88130 2018-12-03T22:07:41 Z KCSC Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 444 ms 70876 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

struct Node {
	int mxm;
	long long sum; } sgt[DIM << 2];

void update1(int nd, int le, int ri, int ps, int vl) {
	if (le == ri) {
		sgt[nd] = {vl, vl}; }
	else {
		int md = (le + ri) / 2;
		if (ps <= md) {
			update1(nd << 1, le, md, ps, vl); }
		else {
			update1(nd << 1 | 1, md + 1, ri, ps, vl); }
		sgt[nd] = {max(sgt[nd << 1].mxm, sgt[nd << 1 | 1].mxm),
				   sgt[nd << 1].sum + sgt[nd << 1 | 1].sum}; } }

void update2(int nd, int le, int ri, int st, int en, int k) {
	if (sgt[nd].mxm == 0 or k == 1) {
		return; }
	if (le == ri) {
		sgt[nd] = {sgt[nd].mxm / k, sgt[nd].mxm / k}; }
	else {
		int md = (le + ri) / 2;
		if (st <= md) {
			update2(nd << 1, le, md, st, en, k); }
		if (md <  en) {
			update2(nd << 1 | 1, md + 1, ri, st, en, k); }
		sgt[nd] = {max(sgt[nd << 1].mxm, sgt[nd << 1 | 1].mxm),
				   sgt[nd << 1].sum + sgt[nd << 1 | 1].sum}; } } 

long long query(int nd, int le, int ri, int st, int en) {
	if (st <= le and ri <= en) {
		return sgt[nd].sum; }
	else {
		int md = (le + ri) / 2;
		if (en <= md) {	
			return query(nd << 1, le, md, st, en); }
		if (md <  st) {
			return query(nd << 1 | 1, md + 1, ri, st, en); }
		return query(nd << 1, le, md, st, en) +
			   query(nd << 1 | 1, md + 1, ri, st, en); } }

int main(void) {
#ifdef HOME
	freopen("sterilizing.in", "r", stdin);
	freopen("sterilizing.out", "w", stdout);
#endif
	int n, q, k; cin >> n >> q >> k;
	for (int i = 1; i <= n; ++i) {		
		int x; cin >> x; update1(1, 1, n, i, x); }
	while (q--) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) {
			update1(1, 1, n, x, y); }
		if (t == 2) {	
			update2(1, 1, n, x, y, k); }
		if (t == 3) {
			cout << query(1, 1, n, x, y) << "\n"; } }		
	return 0; }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 5 ms 548 KB Output is correct
3 Correct 4 ms 824 KB Output is correct
4 Correct 10 ms 824 KB Output is correct
5 Correct 11 ms 1088 KB Output is correct
6 Correct 11 ms 1088 KB Output is correct
7 Correct 11 ms 1284 KB Output is correct
8 Correct 11 ms 1284 KB Output is correct
9 Correct 12 ms 1296 KB Output is correct
10 Correct 10 ms 1380 KB Output is correct
11 Correct 11 ms 1576 KB Output is correct
12 Correct 11 ms 1576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5880 KB Output is correct
2 Correct 175 ms 7476 KB Output is correct
3 Correct 162 ms 11180 KB Output is correct
4 Correct 205 ms 13360 KB Output is correct
5 Correct 250 ms 15976 KB Output is correct
6 Correct 247 ms 18288 KB Output is correct
7 Correct 260 ms 20744 KB Output is correct
8 Correct 260 ms 23200 KB Output is correct
9 Correct 242 ms 25604 KB Output is correct
10 Correct 239 ms 27952 KB Output is correct
11 Correct 233 ms 30140 KB Output is correct
12 Correct 236 ms 32512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 32512 KB Output is correct
2 Correct 45 ms 32512 KB Output is correct
3 Correct 61 ms 32512 KB Output is correct
4 Correct 173 ms 32512 KB Output is correct
5 Correct 220 ms 36064 KB Output is correct
6 Correct 228 ms 37488 KB Output is correct
7 Correct 218 ms 38960 KB Output is correct
8 Correct 225 ms 40212 KB Output is correct
9 Correct 203 ms 41504 KB Output is correct
10 Correct 205 ms 42804 KB Output is correct
11 Correct 212 ms 44060 KB Output is correct
12 Correct 200 ms 45444 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 45444 KB Output is correct
2 Correct 227 ms 46920 KB Output is correct
3 Correct 204 ms 47932 KB Output is correct
4 Correct 261 ms 48724 KB Output is correct
5 Correct 321 ms 54316 KB Output is correct
6 Correct 347 ms 56672 KB Output is correct
7 Correct 326 ms 59124 KB Output is correct
8 Correct 386 ms 61728 KB Output is correct
9 Correct 358 ms 63940 KB Output is correct
10 Correct 383 ms 66340 KB Output is correct
11 Correct 325 ms 68568 KB Output is correct
12 Correct 444 ms 70876 KB Output is correct