oj.uz

Submission #776378

# Submission time Handle Problem Language Result Execution time Memory
776378 2023-07-07T19:06:40 Z hyakup Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 225 ms 10248 KB 
#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 );
      |                       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory 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