Submission #103551

#	Time	Username	Problem	Language	Result	Execution time	Memory
103551		Minnakhmetov	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1794 ms	39928 KiB

sterilizing

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 1e5 + 5, LOG = 32;
ll sum[N << 2];
int rest[N << 2][LOG], up[N << 2], a[N];
int n, q, k;

void push(int v, int L, int R) {
	if (up[v]) {
		if (L != R) {
			up[v * 2] += up[v];
			up[v * 2 + 1] += up[v];
		}
		for (int i = 0; i < min(LOG, up[v]); i++) {
			sum[v] -= rest[v][i];
			sum[v] /= k;
		}
		for (int i = 0; i < LOG; i++) {
			rest[v][i] = up[v] + i >= LOG ? 0 : rest[v][i + up[v]];
		}
		up[v] = 0;
	}
}

void mrg(int v) {
	sum[v] = sum[v * 2] + sum[v * 2 + 1];
	for (int i = 0; i < LOG; i++)
		rest[v][i] = rest[v * 2][i] + rest[v * 2 + 1][i];
}

void build(int v, int L, int R) {
	if (L == R) {
		int y = a[L];
		sum[v] = y;
		for (int i = 0; i < LOG; i++) {
			rest[v][i] = y % k;
			y /= k;
		}
	}
	else {
		int m = (L + R) >> 1;
		build(v * 2, L, m);
		build(v * 2 + 1, m + 1, R);
		mrg(v);
	}
}

void upd(int x, int y, int v = 1, int L = 0, int R = n - 1) {
	push(v, L, R);
	if (x < L || x > R)
		return;
	if (L == R) {
		sum[v] = y;
		for (int i = 0; i < LOG; i++) {
			rest[v][i] = y % k;
			y /= k;
		}
	}
	else {
		int m = (L + R) >> 1;
		upd(x, y, v * 2, L, m);
		upd(x, y, v * 2 + 1, m + 1, R);
		mrg(v);
	}
}

void spray(int l, int r, int v = 1, int L = 0, int R = n - 1) {
	push(v, L, R);
	if (l > r)
		return;
	if (l == L && r == R) {
		up[v]++;
		push(v, L, R);
	}
	else {
		int m = (L + R) >> 1;
		spray(l, min(m, r), v * 2, L, m);
		spray(max(m + 1, l), r, v * 2 + 1, m + 1, R);
		mrg(v);
	}
}

ll que(int l, int r, int v = 1, int L = 0, int R = n - 1) {
	push(v, L, R);
	if (l > r)
		return 0;
	if (l == L && r == R)
		return sum[v];
	int m = (L + R) >> 1;
	return que(l, min(m, r), v * 2, L, m) +
		que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q >> k;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	build(1, 0, n - 1);

	while (q--) {
		int type, x, y;
		cin >> type >> x >> y;

		if (type == 1) {
			upd(x - 1, y);
		}
		else if (type == 2) {
			spray(x - 1, y - 1);
		}
		else {
			cout << que(x - 1, y - 1) << "\n";
		}
	}

	return 0;
}

Compilation message (stderr)

sterilizing.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

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