oj.uz

Submission #29791

# Submission time Handle Problem Language Result Execution time Memory
29791 2017-07-20T17:56:47 Z samir_droubi Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 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]);
        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 )
        {
            s.insert(l);
            update( 1 , 1 , n , l , r );
        }
        if( ty == 2 )
            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 6 ms 5540 KB Output is correct
3 Correct 3 ms 5672 KB Output is correct
4 Correct 3 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 9 ms 5672 KB Output is correct
9 Correct 9 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 6 ms 5672 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 7784 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5804 KB Output is correct
2 Correct 39 ms 7652 KB Output is correct
3 Correct 53 ms 7784 KB Output is correct
4 Correct 86 ms 6868 KB Output is correct
5 Correct 159 ms 10432 KB Output is correct
6 Correct 153 ms 10432 KB Output is correct
7 Execution timed out 5000 ms 10436 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 8056 KB Output is correct
2 Correct 203 ms 8048 KB Output is correct
3 Correct 336 ms 7652 KB Output is correct
4 Correct 223 ms 7124 KB Output is correct
5 Correct 363 ms 10436 KB Output is correct
6 Correct 456 ms 10292 KB Output is correct
7 Correct 376 ms 10292 KB Output is correct
8 Correct 603 ms 10292 KB Output is correct
9 Correct 459 ms 11084 KB Output is correct
10 Correct 533 ms 10824 KB Output is correct
11 Correct 396 ms 11084 KB Output is correct
12 Correct 743 ms 10824 KB Output is correct