oj.uz

Submission #153926

# Submission time Handle Problem Language Result Execution time Memory
153926 2019-09-17T14:05:01 Z georgerapeanu Sterilizing Spray (JOI15_sterilizing) C++11
10 / 100
 210 ms 9464 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

struct node_t{
    long long sum;
    int cnt;
    int mi;
    int ma;
    int 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;
    }
};

int n,q,k;

node_t aint[4 * NMAX + 5];

void propag(int nod,int st,int 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(int nod,int st,int dr){
    if(st == dr){
        int val;
        scanf("%d",&val);
        aint[nod].sum = aint[nod].mi = aint[nod].ma = val;
        aint[nod].cnt = 1;
        return ;
    }

    int 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(int nod,int st,int dr,int pos,int 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 ;
    }

    int 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(int nod,int st,int dr,int l,int 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 ;
    }

    int 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(int nod,int st,int dr,int l,int r){
    propag(nod,st,dr);

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

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

    int mid = (st + dr) / 2;

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

int main(){

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

    build(1,1,n);

    while(q--){
        int t,a,b;
        
        scanf("%d %d %d",&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(int, int, int)':
sterilizing.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&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("%d %d %d",&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("%d %d %d",&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 396 KB Output is correct
4 Incorrect 9 ms 488 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 93 ms 5752 KB Output is correct
2 Correct 82 ms 5500 KB Output is correct
3 Correct 77 ms 8440 KB Output is correct
4 Correct 105 ms 8952 KB Output is correct
5 Correct 129 ms 9464 KB Output is correct
6 Correct 122 ms 9416 KB Output is correct
7 Correct 115 ms 9368 KB Output is correct
8 Correct 113 ms 9336 KB Output is correct
9 Correct 105 ms 9336 KB Output is correct
10 Correct 105 ms 9336 KB Output is correct
11 Correct 105 ms 9264 KB Output is correct
12 Correct 104 ms 9232 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5096 KB Output is correct
2 Incorrect 210 ms 5380 KB Output isn't correct
3 Halted 0 ms 0 KB -