oj.uz

Submission #211191

# Submission time Handle Problem Language Result Execution time Memory
211191 2020-03-19T11:43:38 Z DodgeBallMan Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 286 ms 5368 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, q;
long long seg[N<<2], k;

void update( int pos, long long val, int l = 1, int r = n, int idx = 1 ) {
    if( l > pos || r < pos ) return ;
    if( l == r ) return void( seg[idx] = val );
    int m = l + r >> 1;
    if( pos <= m ) update( pos, val, l, m, idx<<1 );
    else update( pos, val, m+1, r, idx<<1|1 );
    seg[idx] = seg[idx<<1] + seg[idx<<1|1];
}

void spray( int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
    if( k == 1 ) return ;
    if( !seg[idx] ) return ;
    if( l > rr || r < ll ) return ;
    if( l == r ) return void( seg[idx] /= k );
    int m = l + r >> 1;
    spray( ll, rr, l, m, idx<<1 ), spray( ll, rr, m+1, r, idx<<1|1 );
    seg[idx] = seg[idx<<1] + seg[idx<<1|1];
}

long long query( int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
    if( l > rr || r < ll ) return 0;
    if( l >= ll && r <= rr ) return seg[idx];
    int m = l + r >> 1;
    return query( ll, rr, l, m, idx<<1 ) + query( ll, rr, m+1, r, idx<<1|1 );
}

int main()
{
    scanf("%d %d %lld",&n,&q,&k);
    for( int i = 1 ; i <= n ; i++ ) {
        long long a;
        scanf("%lld",&a);
        update( i, a );
    }
    while( q-- ) {
        int t, a, b;
        scanf("%d %d %d",&t,&a,&b);
        if( t == 1 ) update( a, ( long long )b );
        else if( t == 2 ) spray( a, b );
        else printf("%lld\n",query( a, b ));
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'void update(int, long long int, int, int, int)':
sterilizing.cpp:12:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
sterilizing.cpp: In function 'void spray(int, int, int, int, int)':
sterilizing.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
sterilizing.cpp: In function 'long long int query(int, int, int, int, int)':
sterilizing.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:37:10: 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:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&t,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 8 ms 512 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 12 ms 388 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 8 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1936 KB Output is correct
2 Correct 65 ms 1788 KB Output is correct
3 Correct 65 ms 2680 KB Output is correct
4 Correct 83 ms 2936 KB Output is correct
5 Correct 98 ms 5240 KB Output is correct
6 Correct 99 ms 5356 KB Output is correct
7 Correct 106 ms 5368 KB Output is correct
8 Correct 103 ms 5368 KB Output is correct
9 Correct 94 ms 5368 KB Output is correct
10 Correct 97 ms 5240 KB Output is correct
11 Correct 99 ms 5112 KB Output is correct
12 Correct 91 ms 5240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 512 KB Output is correct
2 Correct 23 ms 1408 KB Output is correct
3 Correct 30 ms 1408 KB Output is correct
4 Correct 65 ms 896 KB Output is correct
5 Correct 96 ms 2552 KB Output is correct
6 Correct 95 ms 3832 KB Output is correct
7 Correct 87 ms 4088 KB Output is correct
8 Correct 92 ms 3864 KB Output is correct
9 Correct 86 ms 3704 KB Output is correct
10 Correct 85 ms 3704 KB Output is correct
11 Correct 85 ms 3736 KB Output is correct
12 Correct 89 ms 3832 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1528 KB Output is correct
2 Correct 118 ms 1528 KB Output is correct
3 Correct 127 ms 1528 KB Output is correct
4 Correct 146 ms 1116 KB Output is correct
5 Correct 171 ms 2808 KB Output is correct
6 Correct 187 ms 5112 KB Output is correct
7 Correct 165 ms 5136 KB Output is correct
8 Correct 216 ms 5112 KB Output is correct
9 Correct 198 ms 4984 KB Output is correct
10 Correct 226 ms 5144 KB Output is correct
11 Correct 173 ms 4980 KB Output is correct
12 Correct 286 ms 5112 KB Output is correct