#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, Q, K;
int C[100010];
struct node {
ll sum;
deque<int> dq;
};
node mrg(node &a, node &b) {
node ret;
ret.sum = a.sum + b.sum;
for(int i = 0; i < min(a.dq.size(), b.dq.size()); i++) {
ret.dq.push_back(a.dq[i] + b.dq[i]);
}
for(int i = min(a.dq.size(), b.dq.size()); i < a.dq.size(); i++) {
ret.dq.push_back(a.dq[i]);
}
for(int i = min(a.dq.size(), b.dq.size()); i < b.dq.size(); i++) {
ret.dq.push_back(b.dq[i]);
}
return ret;
}
struct BIT {
vector<node> tree;
vector<int> lazy;
void init() {
tree = vector<node>(4 * N);
lazy = vector<int>(4 * N, 0);
build(0, N - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n].sum = C[l];
while(C[l]) tree[n].dq.push_back(C[l] % K), C[l] /= K;
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = mrg(tree[2*n], tree[2*n + 1]);
}
void prop(int l, int r, int n) {
if(l != r) {
lazy[2*n] += lazy[n];
lazy[2*n + 1] += lazy[n];
while(lazy[n]) {
if(!tree[2*n].dq.size() && !tree[2*n + 1].dq.size()) break;
if(tree[2*n].dq.size()) {
tree[2*n].sum -= tree[2*n].dq.front(); tree[2*n].dq.pop_front();
tree[2*n].sum /= K;
}
if(tree[2*n + 1].dq.size()) {
tree[2*n + 1].sum -= tree[2*n + 1].dq.front(); tree[2*n + 1].dq.pop_front();
tree[2*n + 1].sum /= K;
}
lazy[n]--;
}
lazy[n] = 0;
}
}
void upd1(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n].sum = val;
while(!tree[n].dq.empty()) tree[n].dq.pop_back();
while(val) tree[n].dq.push_back(val % K), val /= K;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd1(idx, val, l, m, 2*n);
upd1(idx, val, m + 1, r, 2*n + 1);
tree[n] = mrg(tree[2*n], tree[2*n + 1]);
}
void upd2(int a, int b, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
if(!tree[n].dq.empty()) {
tree[n].sum -= tree[n].dq.front(); tree[n].dq.pop_front();
tree[n].sum /= K;
}
lazy[n]++;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd2(a, b, l, m, 2*n);
upd2(a, b, m + 1, r, 2*n + 1);
tree[n] = mrg(tree[2*n], tree[2*n + 1]);
}
ll quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n].sum;
prop(l, r, n);
int m = (l + r)>>1;
ll L = quer(a, b, l, m, 2*n);
ll R = quer(a, b, m + 1, r, 2*n + 1);
return L + R;
}
} bit;
int main() {
scanf("%d %d %d", &N, &Q, &K);
for(int i = 0; i < N; i++) {
scanf("%d", &C[i]);
}
bit.init();
for(int i = 0; i < Q; i++) {
int t, a, b; scanf("%d %d %d", &t, &a, &b);
if(t == 1) {
a--;
bit.upd1(a, b, 0, N - 1, 1);
}
if(t == 2) {
a--; b--;
bit.upd2(a, b, 0, N - 1, 1);
}
if(t == 3) {
a--; b--;
printf("%lld\n", bit.quer(a, b, 0, N - 1, 1));
}
}
}
Compilation message
sterilizing.cpp: In function 'node mrg(node&, node&)':
sterilizing.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < min(a.dq.size(), b.dq.size()); i++) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:21:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = min(a.dq.size(), b.dq.size()); i < a.dq.size(); i++) {
~~^~~~~~~~~~~~~
sterilizing.cpp:24:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = min(a.dq.size(), b.dq.size()); i < b.dq.size(); i++) {
~~^~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &Q, &K);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &C[i]);
~~~~~^~~~~~~~~~~~~
sterilizing.cpp:119:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t, a, b; scanf("%d %d %d", &t, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
632 KB |
Output is correct |
| 2 |
Execution timed out |
5099 ms |
524292 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5145 ms |
524292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
524292 KB |
Output is correct |
| 2 |
Correct |
260 ms |
524292 KB |
Output is correct |
| 3 |
Correct |
347 ms |
524292 KB |
Output is correct |
| 4 |
Correct |
653 ms |
524292 KB |
Output is correct |
| 5 |
Correct |
1193 ms |
524292 KB |
Output is correct |
| 6 |
Correct |
1174 ms |
524292 KB |
Output is correct |
| 7 |
Execution timed out |
5112 ms |
524292 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
835 ms |
524292 KB |
Output is correct |
| 2 |
Correct |
947 ms |
524292 KB |
Output is correct |
| 3 |
Correct |
930 ms |
524292 KB |
Output is correct |
| 4 |
Correct |
1034 ms |
524292 KB |
Output is correct |
| 5 |
Correct |
1441 ms |
524292 KB |
Output is correct |
| 6 |
Correct |
1598 ms |
524292 KB |
Output is correct |
| 7 |
Correct |
1422 ms |
524292 KB |
Output is correct |
| 8 |
Correct |
1698 ms |
524292 KB |
Output is correct |
| 9 |
Correct |
1237 ms |
524292 KB |
Output is correct |
| 10 |
Correct |
1274 ms |
524292 KB |
Output is correct |
| 11 |
Correct |
1169 ms |
524292 KB |
Output is correct |
| 12 |
Correct |
1558 ms |
524292 KB |
Output is correct |
