// 15.22
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111
#define logn 35
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
ll K;
ll arr[maxn];
struct segtree{
ll seg[4 * maxn][logn];
int lazy[4 * maxn];
void push(int x, int l, int d){
if(lazy[x] == 0)
return;
int k = lazy[x];
for(int i = 0; i + k < logn; i++)
seg[x][i] = seg[x][i + k];
for(int i = logn - k; i < logn; i++)
seg[x][i] = 0;
if(l != d){
lazy[2 * x] += lazy[x];
lazy[2 * x + 1] += lazy[x];
}
lazy[x] = 0;
}
void combine(int x, int l, int d){
for(int i = 0; i < logn; i++)
seg[x][i] = seg[l][i] + seg[d][i];
}
void setValue(int x, ll val){
seg[x][0] = val;
for(int i = 1; i < logn; i++)
seg[x][i] = seg[x][i - 1] / K;
}
void build(int x, int l, int d){
if(l > d)
return;
if(l == d){
setValue(x, arr[l]);
lazy[x] = 0;
return;
}
int mid = (l + d) / 2;
build(2 * x, l, mid);
build(2 * x + 1, mid + 1, d);
combine(x, 2 * x, 2 * x + 1);
lazy[x] = 0;
}
void update(int x, int l, int d, int i, ll val){
push(x, l, d);
if(l > d || l > i || d < i)
return;
if(l == d && l == i){
setValue(x, val);
return;
}
int mid = (l + d) / 2;
update(2 * x, l, mid, i, val);
update(2 * x + 1, mid + 1, d, i, val);
combine(x, 2 * x, 2 * x + 1);
}
void reduce(int x, int l, int d, int i, int j){
push(x, l, d);
if(l > d || l > j || d < i)
return;
if(i <= l && d <= j){
lazy[x] += 1;
push(x, l, d);
return;
}
int mid = (l + d) / 2;
reduce(2 * x, l, mid, i, j);
reduce(2 * x + 1, mid + 1, d, i, j);
combine(x, 2 * x, 2 * x + 1);
}
ll query(int x, int l, int d, int i, int j){
push(x, l, d);
if(l > d || l > j || d < i)
return 0;
if(i <= l && d <= j)
return seg[x][0];
int mid = (l + d) / 2;
ll ret = query(2 * x, l, mid, i, j);
ret += query(2 * x + 1, mid + 1, d, i, j);
return ret;
}
}seg;
int main(){
int n, q;
scanf("%d%d%lld", &n, &q, &K);
for(int i = 1; i <= n; i++)
scanf("%lld", arr + i);
seg.build(1, 1, n);
while(q--){
ll t, x, y;
scanf("%lld%lld%lld", &t, &x, &y);
if(t == 1)
seg.update(1, 1, n, x, y);
if(t == 2)
seg.reduce(1, 1, n, x, y);
if(t == 3)
printf("%lld\n", seg.query(1, 1, n, x, y));
}
return 0;
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &n, &q, &K);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", arr + i);
~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &t, &x, &y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1270 ms |
37532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
37532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
980 ms |
37720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
