oj.uz

답안 #1034131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034131 2024-07-25T09:59:18 Z juicy Sterilizing Spray (JOI15_sterilizing) C++17
20 / 100
 314 ms 64864 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;
		}
	}
	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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 33416 KB Output is correct
2 Correct 40 ms 19792 KB Output is correct
3 Correct 63 ms 63828 KB Output is correct
4 Correct 92 ms 64336 KB Output is correct
5 Correct 88 ms 64848 KB Output is correct
6 Correct 81 ms 64848 KB Output is correct
7 Correct 80 ms 64864 KB Output is correct
8 Correct 84 ms 64852 KB Output is correct
9 Correct 77 ms 64592 KB Output is correct
10 Correct 97 ms 64808 KB Output is correct
11 Correct 74 ms 64592 KB Output is correct
12 Correct 75 ms 64596 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 4700 KB Output is correct
2 Correct 73 ms 31828 KB Output is correct
3 Correct 82 ms 31932 KB Output is correct
4 Correct 149 ms 17232 KB Output is correct
5 Correct 255 ms 64296 KB Output is correct
6 Correct 314 ms 64432 KB Output is correct
7 Correct 75 ms 63568 KB Output is correct
8 Correct 262 ms 64344 KB Output is correct
9 Correct 216 ms 64152 KB Output is correct
10 Correct 222 ms 64340 KB Output is correct
11 Correct 219 ms 64336 KB Output is correct
12 Correct 215 ms 64336 KB Output is correct

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 153 ms 33360 KB Output isn't correct
2 Halted 0 ms 0 KB -