oj.uz

Submission #750164

# Submission time Handle Problem Language Result Execution time Memory
750164 2023-05-29T07:25:04 Z Muaath_5 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 92 ms 8536 KB 
#include <bits/stdc++.h>
#define ll long long
#define umin(x, y) x = min(x, y)
#define sq(x) ((x)*(x))
using namespace std;

const int N = 1e5+5;

int n, q, k, c[N];

ll tree[4 * N];
ll modsum[4 * N];
int lazy[4 * N];

inline void pushdown(int node, int l=-1, int r=-1)
{
	if (lazy[node]) {
		//if (node == 9 || node == 10)
		//	n = n;
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
		modsum[node] /= pow(k, lazy[node]);
		tree[node] = modsum[node];
		lazy[node] = 0;
	}
}

void build(int l=0, int r=N-1, int node=1)
{
	if (l == r) {
		tree[node] = c[l];
		modsum[node] = c[l] - (c[l] % k);
		return;
	}
	const int mid = (l + r) / 2;
	build(l, mid, node*2);
	build(mid + 1, r, node*2+1);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	modsum[node] = modsum[node * 2] + modsum[node * 2 + 1];
}

void update(int idx, int val, int l =0, int r = N-1, int node=1)
{
	pushdown(node);
	if (l == r) {
		tree[node] = val;
		modsum[node] = val - (val % k);
		lazy[node] = 0;
		return;
	}
	const int mid = (l + r) / 2;
	if (idx <= mid)
		update(idx, val, l, mid, node*2);
	else
		update(idx, val, mid + 1, r, node*2+1);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	modsum[node] = modsum[node * 2] + modsum[node * 2 + 1];
}

void lazy_update(int ql, int qr, int l=0, int r=N-1, int node=1)
{
	pushdown(node, l, r);
	if (r < ql || l > qr) return;
	if (ql <= l && r <= qr) {
		lazy[node]++;
		pushdown(node, l, r);
		pushdown(node * 2);
		pushdown(node * 2 + 1);
		return;
	}
	const int mid = (l + r) / 2;
	lazy_update(ql, qr, l, mid, node * 2);
	lazy_update(ql, qr, mid + 1, r, node * 2 + 1);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	modsum[node] = modsum[node * 2] + modsum[node * 2 + 1];
}

ll query(int ql, int qr, int l=0, int r=N-1, int node = 1)
{
	pushdown(node);
	if (r < ql || l > qr) return 0;
	if (ql <= l && r <= qr) return tree[node];
	const int mid = (l + r) / 2;
	return
		query(ql, qr, l, mid, node * 2) +
		query(ql, qr, mid + 1, r, node * 2 + 1);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q >> k;
	for (int i = 0; i < n; cin >> c[i++]);
	build();
	while (q--) {
		int cmd, l, r;
		cin >> cmd >> l >> r;
		if (cmd == 1)
			update(l - 1, r);
		else if (cmd == 2)
			;//lazy_update(l - 1, r - 1);
		else
			cout << query(l - 1, r - 1) << '\n';
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5528 KB Output is correct
2 Correct 51 ms 5656 KB Output is correct
3 Correct 59 ms 6132 KB Output is correct
4 Correct 69 ms 7988 KB Output is correct
5 Correct 78 ms 8472 KB Output is correct
6 Correct 68 ms 8408 KB Output is correct
7 Correct 66 ms 8536 KB Output is correct
8 Correct 72 ms 8480 KB Output is correct
9 Correct 67 ms 8380 KB Output is correct
10 Correct 60 ms 8284 KB Output is correct
11 Correct 92 ms 8388 KB Output is correct
12 Correct 62 ms 8320 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 5340 KB Output isn't correct
2 Halted 0 ms 0 KB -