oj.uz

Submission #153931

# Submission time Handle Problem Language Result Execution time Memory
153931 2019-09-17T14:11:06 Z georgerapeanu Sterilizing Spray (JOI15_sterilizing) C++11
10 / 100
 318 ms 11688 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)){
        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:126: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:133: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 5 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Incorrect 14 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6372 KB Output is correct
2 Correct 83 ms 6180 KB Output is correct
3 Correct 81 ms 11384 KB Output is correct
4 Correct 100 ms 11512 KB Output is correct
5 Correct 120 ms 11512 KB Output is correct
6 Correct 119 ms 11688 KB Output is correct
7 Correct 120 ms 11584 KB Output is correct
8 Correct 119 ms 11520 KB Output is correct
9 Correct 108 ms 11640 KB Output is correct
10 Correct 109 ms 11640 KB Output is correct
11 Correct 108 ms 11640 KB Output is correct
12 Correct 121 ms 11668 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1528 KB Output is correct
2 Incorrect 29 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 6652 KB Output is correct
2 Incorrect 318 ms 6724 KB Output isn't correct
3 Halted 0 ms 0 KB -