#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
ll v[maxn];
ll n, q, k;
struct node{
ll sum, maxi; node( ll sum = 0, ll maxi = 0 ) : sum(sum), maxi(maxi) {}
node operator + ( node n ){
node resp;
resp.maxi = max( maxi, n.maxi );
resp.sum = sum + n.sum;
return resp;
}
} seg[4*maxn];
void build( int pos, int ini, int fim ){
if( ini == fim ){ seg[pos] = node( v[ini], v[ini] ); return; }
int l = 2*pos, r = 2*pos + 1;
int mid = ( ini + fim )/2;
build( l, ini, mid ); build( r, mid + 1, fim );
seg[pos] = seg[l] + seg[r];
}
void update1( int pos, int ini, int fim, int id, ll val ){
if( ini > id || id > fim ) return;
if( ini == fim ){ seg[pos] = node( val, val ); return; }
int l = 2*pos, r = 2*pos + 1;
int mid = ( ini + fim )/2;
update1( l, ini, mid, id, val ); update1( r, mid + 1, fim, id, val );
seg[pos] = seg[l] + seg[r];
}
void update2( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return;
if( ki <= ini && fim <= kf && seg[pos].maxi == 0 ) return;
if( ini == fim ){ seg[pos].maxi /= k; seg[pos].sum /= k; return; }
int l = 2*pos, r = 2*pos + 1;
int mid = ( ini + fim )/2;
update2( l, ini, mid, ki, kf ); update2( r, mid + 1, fim, ki, kf );
seg[pos] = seg[l] + seg[r];
}
ll query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return 0;
if( ki <= ini && fim <= kf ) return seg[pos].sum;
int l = 2*pos, r = 2*pos + 1;
int mid = ( ini + fim )/2;
return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
int main(){
scanf("%d %d %d", &n, &q, &k );
for( int i = 1; i <= n; i++ ) scanf("%d", &v[i] );
build( 1, 1, n );
while( q-- ){
int t; scanf("%d", &t );
if( t == 1 ){
ll id, val; scanf("%d %d", &id, &val );
update1( 1, 1, n, id, val );
}
if( t == 2 && k != 1 ){
int l, r; scanf("%d %d", &l, &r );
update2( 1, 1, n, l, r );
}
if( t == 3 ){
int l, r; scanf("%d %d", &l, &r );
printf("%lld\n", query( 1, 1, n, l, r ) );
}
}
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:54:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
54 | scanf("%d %d %d", &n, &q, &k );
| ~^ ~~
| | |
| int* long long int*
| %lld
sterilizing.cpp:54:16: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
54 | scanf("%d %d %d", &n, &q, &k );
| ~^ ~~
| | |
| int* long long int*
| %lld
sterilizing.cpp:54:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
54 | scanf("%d %d %d", &n, &q, &k );
| ~^ ~~
| | |
| int* long long int*
| %lld
sterilizing.cpp:55:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
55 | for( int i = 1; i <= n; i++ ) scanf("%d", &v[i] );
| ~^ ~~~~~
| | |
| | long long int*
| int*
| %lld
sterilizing.cpp:60:33: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
60 | ll id, val; scanf("%d %d", &id, &val );
| ~^ ~~~
| | |
| int* long long int*
| %lld
sterilizing.cpp:60:36: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
60 | ll id, val; scanf("%d %d", &id, &val );
| ~^ ~~~~
| | |
| int* long long int*
| %lld
sterilizing.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d %d", &n, &q, &k );
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:55:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | for( int i = 1; i <= n; i++ ) scanf("%d", &v[i] );
| ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:58:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | int t; scanf("%d", &t );
| ~~~~~^~~~~~~~~~~
sterilizing.cpp:60:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | ll id, val; scanf("%d %d", &id, &val );
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | int l, r; scanf("%d %d", &l, &r );
| ~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp:68:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | int l, r; scanf("%d %d", &l, &r );
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
7172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
6620 KB |
Output is correct |
| 2 |
Correct |
14 ms |
6924 KB |
Output is correct |
| 3 |
Correct |
19 ms |
6920 KB |
Output is correct |
| 4 |
Correct |
53 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
69 ms |
7356 KB |
Output is correct |
| 6 |
Correct |
66 ms |
7376 KB |
Output is correct |
| 7 |
Incorrect |
35 ms |
7380 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
7124 KB |
Output is correct |
| 2 |
Correct |
100 ms |
7152 KB |
Output is correct |
| 3 |
Correct |
97 ms |
6944 KB |
Output is correct |
| 4 |
Correct |
107 ms |
7064 KB |
Output is correct |
| 5 |
Correct |
124 ms |
7584 KB |
Output is correct |
| 6 |
Correct |
156 ms |
7608 KB |
Output is correct |
| 7 |
Correct |
119 ms |
7608 KB |
Output is correct |
| 8 |
Correct |
175 ms |
7588 KB |
Output is correct |
| 9 |
Correct |
153 ms |
7644 KB |
Output is correct |
| 10 |
Correct |
172 ms |
7608 KB |
Output is correct |
| 11 |
Correct |
126 ms |
7596 KB |
Output is correct |
| 12 |
Correct |
219 ms |
7584 KB |
Output is correct |
