#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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
300 ms |
3232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
990 ms |
20520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
