#include <bits/stdc++.h>
#define ser stderr
typedef long long ll;
using namespace std;
const int MAXN = 100010;
const int MAXL = 31;
int n, q;
ll k;
ll seg[4 * MAXN][MAXL];
int lz[4 * MAXN];
void refresh(int pos, int ini, int fim){
if(lz[pos] == 0) return;
int m = (ini + fim) / 2;
int e = 2 * pos, d = 2 * pos + 1;
lz[e] += lz[pos], lz[d] += lz[pos];
int l = lz[pos];
lz[pos] = 0;
for(int i = 0; i < MAXL; i++){
seg[pos][i] = seg[pos][i + l];
}
return;
}
void merge(int pos, int ini, int fim){
int m = (ini + fim) / 2;
int e = 2 * pos, d = 2 * pos + 1;
for(int i = 0; i < MAXL; i++){
seg[pos][i] = seg[e][i] + seg[d][i];
}
return;
}
void update1(int pos, int ini, int fim, int id, ll val){
refresh(pos, ini, fim);
if(id < ini || id > fim) return;
if(ini == fim){
for(int i = 0; i < MAXL; i++){
seg[pos][i] = val;
val /= k;
}
return;
}
int m = (ini + fim) / 2;
int e = 2 * pos, d = 2 * pos + 1;
update1(e, ini, m, id, val);
update1(d, m + 1, fim, id, val);
merge(pos, ini, fim);
return;
}
void update2(int pos, int ini, int fim, int l, int r){
refresh(pos, ini, fim);
if(l > fim || r < ini) return;
if(l <= ini && fim <= r){
lz[pos]++;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) / 2;
int e = 2 * pos, d = 2 * pos + 1;
update2(e, ini, m, l, r);
update2(d, m + 1, fim, l, r);
}
ll query(int pos, int ini, int fim, int l, int r){
if(l > fim || r < ini) return 0;
refresh(pos, ini, fim);
if(l <= ini && fim <= r) return seg[pos][0];
int m = (ini + fim) / 2.;
int e = 2 * pos, d = 2 * pos + 1;
return query(e, ini, m, l, r) + query(d, m + 1, fim, l, r);
}
int main(){
scanf("%d %d %d", &n, &q, &k);
for(int i = 1; i <= n; i++){
ll v; scanf("%lld", &v);
update1(1, 1, n, i, v);
}
for(int i = 1; i <= q; i++){
int type; scanf("%d", &type);
if(type == 1){
int a;
ll b;
scanf("%d %lld", &a, &b);
update1(1, 1, n, a, b);
}
if(type == 2){
int l, r; scanf("%d %d", &l, &r);
update2(1, 1, n, l, r);
}
if(type == 3){
int l, r; scanf("%d %d", &l, &r);
ll resp = query(1, 1, n, l, r);
printf("%lld\n", resp);
}
}
return 0;
}
Compilation message
sterilizing.cpp: In function 'void refresh(int, int, int)':
sterilizing.cpp:17:9: warning: unused variable 'm' [-Wunused-variable]
17 | int m = (ini + fim) / 2;
| ^
sterilizing.cpp: In function 'void merge(int, int, int)':
sterilizing.cpp:32:9: warning: unused variable 'm' [-Wunused-variable]
32 | int m = (ini + fim) / 2;
| ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:91:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
91 | scanf("%d %d %d", &n, &q, &k);
| ~^ ~~
| | |
| int* ll* {aka long long int*}
| %lld
sterilizing.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d %d %d", &n, &q, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:94:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | ll v; scanf("%lld", &v);
| ~~~~~^~~~~~~~~~~~
sterilizing.cpp:99:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | int type; scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d %lld", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:107:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | int l, r; scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:111:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | int l, r; scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
33552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
4424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
33328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
