#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 ){
int l, r; scanf("%d %d", &l, &r );
if( k == 1 ) continue;
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:69:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | int l, r; scanf("%d %d", &l, &r );
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
6 ms |
6484 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
6484 KB |
Output is correct |
| 7 |
Correct |
5 ms |
6484 KB |
Output is correct |
| 8 |
Correct |
6 ms |
6484 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6484 KB |
Output is correct |
| 10 |
Correct |
5 ms |
6484 KB |
Output is correct |
| 11 |
Correct |
6 ms |
6596 KB |
Output is correct |
| 12 |
Correct |
6 ms |
6484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
7372 KB |
Output is correct |
| 2 |
Correct |
43 ms |
7160 KB |
Output is correct |
| 3 |
Correct |
43 ms |
7436 KB |
Output is correct |
| 4 |
Correct |
48 ms |
7680 KB |
Output is correct |
| 5 |
Correct |
58 ms |
10188 KB |
Output is correct |
| 6 |
Correct |
61 ms |
10228 KB |
Output is correct |
| 7 |
Correct |
57 ms |
10248 KB |
Output is correct |
| 8 |
Correct |
57 ms |
10200 KB |
Output is correct |
| 9 |
Correct |
53 ms |
10048 KB |
Output is correct |
| 10 |
Correct |
57 ms |
10032 KB |
Output is correct |
| 11 |
Correct |
54 ms |
10120 KB |
Output is correct |
| 12 |
Correct |
69 ms |
10064 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
6632 KB |
Output is correct |
| 2 |
Correct |
15 ms |
6920 KB |
Output is correct |
| 3 |
Correct |
22 ms |
6868 KB |
Output is correct |
| 4 |
Correct |
53 ms |
6784 KB |
Output is correct |
| 5 |
Correct |
71 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
67 ms |
7356 KB |
Output is correct |
| 7 |
Correct |
49 ms |
7468 KB |
Output is correct |
| 8 |
Correct |
69 ms |
8728 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8600 KB |
Output is correct |
| 10 |
Correct |
61 ms |
8608 KB |
Output is correct |
| 11 |
Correct |
62 ms |
8620 KB |
Output is correct |
| 12 |
Correct |
64 ms |
8600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
85 ms |
7032 KB |
Output is correct |
| 2 |
Correct |
88 ms |
7064 KB |
Output is correct |
| 3 |
Correct |
98 ms |
7032 KB |
Output is correct |
| 4 |
Correct |
108 ms |
7088 KB |
Output is correct |
| 5 |
Correct |
124 ms |
7500 KB |
Output is correct |
| 6 |
Correct |
141 ms |
7592 KB |
Output is correct |
| 7 |
Correct |
122 ms |
7536 KB |
Output is correct |
| 8 |
Correct |
167 ms |
7548 KB |
Output is correct |
| 9 |
Correct |
151 ms |
7588 KB |
Output is correct |
| 10 |
Correct |
164 ms |
7628 KB |
Output is correct |
| 11 |
Correct |
129 ms |
7544 KB |
Output is correct |
| 12 |
Correct |
225 ms |
7772 KB |
Output is correct |
