oj.uz

Submission #103551

# Submission time Handle Problem Language Result Execution time Memory
103551 2019-03-31T12:30:58 Z Minnakhmetov Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1794 ms 39928 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 18 ms 1024 KB Output is correct
5 Correct 25 ms 1536 KB Output is correct
6 Correct 22 ms 1536 KB Output is correct
7 Correct 21 ms 1536 KB Output is correct
8 Correct 22 ms 1536 KB Output is correct
9 Correct 25 ms 1536 KB Output is correct
10 Correct 23 ms 1536 KB Output is correct
11 Correct 23 ms 1640 KB Output is correct
12 Correct 25 ms 1644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1460 ms 20600 KB Output is correct
2 Correct 1199 ms 14328 KB Output is correct
3 Correct 1024 ms 38820 KB Output is correct
4 Correct 1406 ms 39288 KB Output is correct
5 Correct 1777 ms 39900 KB Output is correct
6 Correct 1794 ms 39928 KB Output is correct
7 Correct 1755 ms 39752 KB Output is correct
8 Correct 1754 ms 39928 KB Output is correct
9 Correct 988 ms 39544 KB Output is correct
10 Correct 1037 ms 39428 KB Output is correct
11 Correct 1014 ms 39584 KB Output is correct
12 Correct 1006 ms 39772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 2780 KB Output is correct
2 Correct 259 ms 18652 KB Output is correct
3 Correct 381 ms 18552 KB Output is correct
4 Correct 1165 ms 9736 KB Output is correct
5 Correct 1743 ms 36984 KB Output is correct
6 Correct 1668 ms 36856 KB Output is correct
7 Correct 1734 ms 38008 KB Output is correct
8 Correct 1650 ms 38520 KB Output is correct
9 Correct 929 ms 38284 KB Output is correct
10 Correct 950 ms 38264 KB Output is correct
11 Correct 953 ms 38260 KB Output is correct
12 Correct 919 ms 38288 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 18788 KB Output is correct
2 Correct 1193 ms 18808 KB Output is correct
3 Correct 711 ms 18688 KB Output is correct
4 Correct 1177 ms 9848 KB Output is correct
5 Correct 1775 ms 37000 KB Output is correct
6 Correct 1691 ms 36996 KB Output is correct
7 Correct 1781 ms 37028 KB Output is correct
8 Correct 1684 ms 37240 KB Output is correct
9 Correct 927 ms 37212 KB Output is correct
10 Correct 1014 ms 37112 KB Output is correct
11 Correct 1014 ms 37240 KB Output is correct
12 Correct 1004 ms 37116 KB Output is correct