oj.uz

Submission #29792

# Submission time Handle Problem Language Result Execution time Memory
29792 2017-07-20T17:59:39 Z samir_droubi Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 186 ms 10292 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;
        if(x) s.insert(l);
        else
        {
            if(s.count(l))
                s.erase(l);
        }
        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]);
        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( 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:43:12: warning: statement has no effect [-Wunused-value]
     for( it; it != s.end() && *it <= r ; ++it )
            ^
sterilizing.cpp:48: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:53: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:56:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
sterilizing.cpp:62: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 5540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7784 KB Output is correct
2 Correct 86 ms 7124 KB Output is correct
3 Correct 96 ms 9236 KB Output is correct
4 Correct 153 ms 10160 KB Output is correct
5 Correct 179 ms 10292 KB Output is correct
6 Correct 183 ms 10292 KB Output is correct
7 Correct 166 ms 10292 KB Output is correct
8 Correct 186 ms 10292 KB Output is correct
9 Correct 149 ms 10292 KB Output is correct
10 Correct 163 ms 10292 KB Output is correct
11 Correct 136 ms 10292 KB Output is correct
12 Correct 153 ms 10292 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 5672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 7916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -