oj.uz

Submission #29793

# Submission time Handle Problem Language Result Execution time Memory
29793 2017-07-20T18:07:38 Z samir_droubi Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 793 ms 11084 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=(1e5)+5;
int n,q,k;
int a[mxn];

set<int>s;
ll st[mxn*4];
void update(int p,int l,int r,int i,int x)
{
    if(r<i||l>i)return;
    if(l==r)
    {
        a[ l ] = x;
        st[ p ] = x;
        return ;
    }
    int md= ( l + r ) / 2;
    if(i<=md)update(p * 2 , l , md , i , x);
    else update( p * 2 + 1 , md + 1 , r , i ,x);
    st[p] = st[ p * 2 ] + st[ p * 2 + 1 ];
}
ll rsq(int p,int l,int r,int i,int j)
{
    if(r<i||l>j)return 0;
    if( l >= i && r <= j)return st[p];
    int md = ( l + r ) / 2;
    ll x = rsq( p * 2 , l , md , i , j );
    ll y = rsq( p * 2 + 1 , md + 1 ,r , i ,j );
    return x + y;
}
void range_update(int l,int r)
{
    set<int>::iterator it = s.lower_bound(l);
    vector<int>in;
    for( it; it != s.end() && *it <= r ; ++it )
    {
        update( 1 , 1 , n , *it , a[*it] / k );
        if( a[*it] == 0 ) in.push_back(*it);
    }
    for(int i = 0 ; i < in.size(); ++i )
        s.erase( in[ i ] );
}
int main()
{
    scanf("%d%d%d",&n,&q,&k);
    for(int i = 1 ; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        if(a[i])s.insert(i);
        update( 1 , 1 , n , i , a[i] );
    }
    while(q--)
    {   
        int ty,l,r;
        scanf("%d%d%d",&ty,&l,&r);
        if( ty == 1 )
        {
            update( 1 , 1 , n , l , r );
            if(r)s.insert(l);
            else
            {
                if(s.count(l))
                    s.erase(l);
            }
        }
        if( ty == 2 && k > 1 )
            range_update( l , r );
        if( ty == 3)
            printf("%lld\n",rsq( 1 , 1 , n , l , r ));
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'void range_update(int, int)':
sterilizing.cpp:37:12: warning: statement has no effect [-Wunused-value]
     for( it; it != s.end() && *it <= r ; ++it )
            ^
sterilizing.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < in.size(); ++i )
                       ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:47:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&q,&k);
                             ^
sterilizing.cpp:50:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
sterilizing.cpp:57:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&ty,&l,&r);
                                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5540 KB Output is correct
2 Correct 0 ms 5540 KB Output is correct
3 Correct 3 ms 5672 KB Output is correct
4 Correct 6 ms 5672 KB Output is correct
5 Correct 9 ms 5672 KB Output is correct
6 Correct 6 ms 5672 KB Output is correct
7 Correct 9 ms 5672 KB Output is correct
8 Correct 3 ms 5672 KB Output is correct
9 Correct 13 ms 5672 KB Output is correct
10 Correct 6 ms 5672 KB Output is correct
11 Correct 6 ms 5672 KB Output is correct
12 Correct 9 ms 5672 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 7784 KB Output is correct
2 Correct 99 ms 7124 KB Output is correct
3 Correct 116 ms 9236 KB Output is correct
4 Correct 153 ms 10160 KB Output is correct
5 Correct 169 ms 10292 KB Output is correct
6 Correct 163 ms 10292 KB Output is correct
7 Correct 176 ms 10292 KB Output is correct
8 Correct 179 ms 10292 KB Output is correct
9 Correct 163 ms 10292 KB Output is correct
10 Correct 159 ms 10292 KB Output is correct
11 Correct 139 ms 10292 KB Output is correct
12 Correct 139 ms 10292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5672 KB Output is correct
2 Correct 29 ms 6596 KB Output is correct
3 Correct 39 ms 6736 KB Output is correct
4 Correct 63 ms 6208 KB Output is correct
5 Correct 123 ms 8084 KB Output is correct
6 Correct 126 ms 7916 KB Output is correct
7 Correct 136 ms 7916 KB Output is correct
8 Correct 106 ms 7916 KB Output is correct
9 Correct 106 ms 8344 KB Output is correct
10 Correct 96 ms 8344 KB Output is correct
11 Correct 106 ms 8340 KB Output is correct
12 Correct 109 ms 8340 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 8056 KB Output is correct
2 Correct 203 ms 8048 KB Output is correct
3 Correct 326 ms 7652 KB Output is correct
4 Correct 209 ms 7124 KB Output is correct
5 Correct 383 ms 10436 KB Output is correct
6 Correct 406 ms 10292 KB Output is correct
7 Correct 329 ms 10292 KB Output is correct
8 Correct 529 ms 10292 KB Output is correct
9 Correct 453 ms 11084 KB Output is correct
10 Correct 546 ms 10824 KB Output is correct
11 Correct 373 ms 11084 KB Output is correct
12 Correct 793 ms 10824 KB Output is correct