oj.uz

Submission #103550

# Submission time Handle Problem Language Result Execution time Memory
103550 2019-03-31T12:28:53 Z Minnakhmetov Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 1817 ms 106744 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; y > 0; 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Runtime error 227 ms 106744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 90948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 2820 KB Output is correct
2 Correct 236 ms 18552 KB Output is correct
3 Correct 349 ms 19072 KB Output is correct
4 Correct 1153 ms 11016 KB Output is correct
5 Correct 1613 ms 38264 KB Output is correct
6 Correct 1687 ms 38272 KB Output is correct
7 Runtime error 173 ms 75424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 18988 KB Output is correct
2 Correct 1241 ms 20760 KB Output is correct
3 Correct 708 ms 20060 KB Output is correct
4 Correct 1220 ms 11528 KB Output is correct
5 Correct 1782 ms 39488 KB Output is correct
6 Correct 1817 ms 39600 KB Output is correct
7 Correct 1777 ms 39416 KB Output is correct
8 Correct 1783 ms 39540 KB Output is correct
9 Correct 1061 ms 39516 KB Output is correct
10 Correct 982 ms 39388 KB Output is correct
11 Correct 955 ms 39424 KB Output is correct
12 Correct 1002 ms 39424 KB Output is correct