oj.uz

Submission #153932

# Submission time Handle Problem Language Result Execution time Memory
153932 2019-09-17T14:12:02 Z georgerapeanu Sterilizing Spray (JOI15_sterilizing) C++11
0 / 100
 5000 ms 6908 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

const long long NMAX = 1e5;

struct node_t{
    long long sum;
    long long cnt;
    long long mi;
    long long ma;
    long long lazy;

    node_t operator + (const node_t &other)const{
        node_t ans;
        ans.sum = this->sum + other.sum;
        ans.cnt = this->cnt + other.cnt;
        ans.mi = min(this->mi,other.mi);
        ans.ma = max(this->ma,other.ma);
        ans.lazy = 0;
        return ans;
    }
};

long long n,q,k;

node_t aint[4 * NMAX + 5];

void propag(long long nod,long long st,long long dr){
    if(st == dr || aint[nod].lazy == 0){
        return ;
    }

    aint[2 * nod].lazy += aint[nod].lazy;
    aint[2 * nod].mi += aint[nod].lazy;
    aint[2 * nod].ma += aint[nod].lazy;
    aint[2 * nod].sum += 1LL * aint[2 * nod].cnt * aint[nod].lazy;

    aint[2 * nod + 1].lazy += aint[nod].lazy;
    aint[2 * nod + 1].mi += aint[nod].lazy;
    aint[2 * nod + 1].ma += aint[nod].lazy;
    aint[2 * nod + 1].sum += 1LL * aint[2 * nod + 1].cnt * aint[nod].lazy;

    aint[nod].lazy = 0;
}

void build(long long nod,long long st,long long dr){
    if(st == dr){
        long long val;
        scanf("%lld",&val);
        aint[nod].sum = aint[nod].mi = aint[nod].ma = val;
        aint[nod].cnt = 1;
        return ;
    }

    long long mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_pos(long long nod,long long st,long long dr,long long pos,long long val){
    propag(nod,st,dr);

    if(st > pos || dr < pos){
        return ;
    }

    if(st == dr){
        aint[nod].sum = aint[nod].mi = aint[nod].ma = val;
        return ;
    }

    long long mid = (st + dr) / 2;

    update_pos(nod * 2,st,mid,pos,val);
    update_pos(nod * 2 + 1,mid + 1,dr,pos,val);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_range(long long nod,long long st,long long dr,long long l,long long r){
    propag(nod,st,dr);

    if(dr < l || st > r){
        return ;
    }

    //if(aint[nod].ma - (aint[nod].ma / k) == aint[nod].mi - (aint[nod].mi / k)){
    if(aint[nod].ma == aint[nod].mi){
        aint[nod].lazy = -aint[nod].ma + (aint[nod].ma / k);
        aint[nod].ma += aint[nod].lazy;
        aint[nod].mi += aint[nod].lazy;
        aint[nod].sum += 1LL * aint[nod].cnt * aint[nod].lazy;
        return ;
    }

    long long mid = (st + dr) / 2;

    update_range(nod * 2,st,mid,l,r);
    update_range(nod * 2 + 1,mid + 1,dr,l,r);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

long long query(long long nod,long long st,long long dr,long long l,long long r){
    propag(nod,st,dr);

    if(dr < l || st > r){
        return 0;
    }

    if(l <= st && dr <= r){
        return aint[nod].sum;
    }

    long long mid = (st + dr) / 2;

    return query(nod * 2,st,mid,l,r) + query(nod * 2 + 1,mid + 1,dr,l,r);
}

int main(){

    scanf("%lld %lld %lld",&n,&q,&k);

    build(1,1,n);

    while(q--){
        long long t,a,b;
        
        scanf("%lld %lld %lld",&t,&a,&b);

        if(t == 1){
            update_pos(1,1,n,a,b);
        }
        else if(t == 2){
            update_range(1,1,n,a,b); 
        }
        else{
            printf("%lld\n",query(1,1,n,a,b));
        }
    }

    return 0;
}

Compilation message

sterilizing.cpp: In function 'void build(long long int, long long int, long long int)':
sterilizing.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&val);
         ~~~~~^~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld",&t,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5026 ms 6908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1272 KB Output is correct
2 Incorrect 25 ms 5624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 5972 KB Output is correct
2 Incorrect 201 ms 6008 KB Output isn't correct
3 Halted 0 ms 0 KB -