oj.uz

Submission #31834

# Submission time Handle Problem Language Result Execution time Memory
31834 2017-09-11T03:40:56 Z Dat160601 Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 686 ms 12332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k,x,y;
long long a[100007],it[400007],mx[400007],lazy[400007];
void init(int p,int l,int r){
    if(l==r){
        it[p]=a[l];
        mx[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(p*2,l,mid);
    init(p*2+1,mid+1,r);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
void dolazy(int p,int l,int r){
    if(lazy[p]==0) return;
    it[p]=0;
    mx[p]=0;
    if(l!=r){
        lazy[p*2]=1;
        lazy[p*2+1]=1;
    }
    lazy[p]=0;
}
void upd(int p,int l,int r,int pos,int val){
    dolazy(p,l,r);
    if(l>pos || r<pos) return;
    if(l==pos && l==r){
        it[p]=val;
        mx[p]=val;
        return;
    }
    int mid=(l+r)/2;
    upd(p*2,l,mid,pos,val);
    upd(p*2+1,mid+1,r,pos,val);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
void div(int p,int l,int r,int L,int R){
    dolazy(p,l,r);
    if(l>R || r<L || l>r) return;
    if(l>=L && r<=R && mx[p]<k){
        it[p]=0;
        mx[p]=0;
        if(l!=r){
            lazy[p*2]=1;
            lazy[p*2+1]=1;
        }
        return;
    }
    if(l==r){
        it[p]=it[p]/k;
        mx[p]=mx[p]/k;
        return;
    }
    int mid=(l+r)/2;
    div(p*2,l,mid,L,R);
    div(p*2+1,mid+1,r,L,R);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
long long get(int p,int l,int r,int L,int R){
    dolazy(p,l,r);
    if(l>R || r<L || l>r) return 0;
    if(l>=L && r<=R){
        //cout<<l<<" "<<r<<" "<<it[p]<<endl;
        return it[p];
    }
    int mid=(l+r)/2;
    return (get(p*2,l,mid,L,R)+get(p*2+1,mid+1,r,L,R));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init(1,1,n);
    int type;
    for(int i=1;i<=q;i++){
        cin>>type>>x>>y;
        if(type==1){
            upd(1,1,n,x,y);
        }
        else if(type==2 && k>1){
            div(1,1,n,x,y);
        }
        else{
            cout<<get(1,1,n,x,y)<<"\n";
        }
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 12332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12332 KB Output is correct
2 Correct 83 ms 12332 KB Output is correct
3 Correct 93 ms 12332 KB Output is correct
4 Correct 239 ms 12332 KB Output is correct
5 Correct 376 ms 12332 KB Output is correct
6 Correct 303 ms 12332 KB Output is correct
7 Incorrect 216 ms 12332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 12332 KB Output is correct
2 Correct 293 ms 12332 KB Output is correct
3 Correct 359 ms 12332 KB Output is correct
4 Correct 366 ms 12332 KB Output is correct
5 Correct 429 ms 12332 KB Output is correct
6 Correct 536 ms 12332 KB Output is correct
7 Correct 429 ms 12332 KB Output is correct
8 Correct 649 ms 12332 KB Output is correct
9 Correct 519 ms 12332 KB Output is correct
10 Correct 686 ms 12332 KB Output is correct
11 Correct 483 ms 12332 KB Output is correct
12 Correct 656 ms 12332 KB Output is correct