제출 #34413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34413		aome	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	613 ms	8816 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, x, a[N];
long long it[2][4 * N];

void build(int i, int l, int r) {
	if (l == r) {
		it[0][i] = it[1][i] = a[l]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);
}

void upd(int i, int l, int r, int p, int x) {
	if (l == r) {
		it[0][i] = it[1][i] = x; return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid) upd(i << 1, l, mid, p, x);
	else upd(i << 1 | 1, mid + 1, r, p, x);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);
}

long long get(int i, int l, int r, int u, int v) {
	if (l > v || u > r) return 0;
	if (u <= l && r <= v) return it[0][i];
	int mid = (l + r) >> 1;
	return get(i << 1, l, mid, u, v) + get(i << 1 | 1, mid + 1, r, u, v);
}

void div(int i, int l, int r, int u, int v) {
	if (l > v || u > r || !it[1][i] || x == 1) return;
	if (l == r) {
		it[0][i] /= x, it[1][i] /= x; return;
	}
	int mid = (l + r) >> 1;
	div(i << 1, l, mid, u, v);
	div(i << 1 | 1, mid + 1, r, u, v);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);	
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> x;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build(1, 1, n);
	while (m--) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) upd(1, 1, n, x, y);
		if (t == 2) div(1, 1, n, x, y);
		if (t == 3) cout << get(1, 1, n, x, y) << '\n'; 
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75