Submission #29793

#	Time	Username	Problem	Language	Result	Execution time	Memory
29793		samir_droubi	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	793 ms	11084 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75