oj.uz

답안 #103547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103547 2019-03-31T12:17:47 Z Minnakhmetov Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 990 ms 91716 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 * 4], 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];
		}
		up[v] = min(up[v], LOG);
		for (int i = 0; i < up[v]; i++) {
			sum[v] -= rest[v][i];
			sum[v] /= k;
		}
		for (int i = 0; i < LOG; i++) {
			rest[v][i] = up[v] + i >= L ? 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 199 ms 91716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 300 ms 3232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 990 ms 20520 KB Output isn't correct
2 Halted 0 ms 0 KB -