oj.uz

Submission #31838

# Submission time Handle Problem Language Result Execution time Memory
31838 2017-09-11T03:50:56 Z Dat160601 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 666 ms 12332 KB 
#include <bits/stdc++.h>
using namespace std;
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]<=1 && k==1) return;
    if(l>=L && r<=R && mx[p]<k){
        if(mx[p]==0) return;
        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]/(long long)k;
        mx[p]=mx[p]/(long long)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){
            div(1,1,n,x,y);
        }
        else{
            cout<<get(1,1,n,x,y)<<"\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12332 KB Output is correct
2 Correct 0 ms 12332 KB Output is correct
3 Correct 0 ms 12332 KB Output is correct
4 Correct 9 ms 12332 KB Output is correct
5 Correct 9 ms 12332 KB Output is correct
6 Correct 6 ms 12332 KB Output is correct
7 Correct 3 ms 12332 KB Output is correct
8 Correct 9 ms 12332 KB Output is correct
9 Correct 13 ms 12332 KB Output is correct
10 Correct 9 ms 12332 KB Output is correct
11 Correct 6 ms 12332 KB Output is correct
12 Correct 19 ms 12332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12332 KB Output is correct
2 Correct 26 ms 12332 KB Output is correct
3 Correct 46 ms 12332 KB Output is correct
4 Correct 163 ms 12332 KB Output is correct
5 Correct 226 ms 12332 KB Output is correct
6 Correct 406 ms 12332 KB Output is correct
7 Correct 306 ms 12332 KB Output is correct
8 Correct 299 ms 12332 KB Output is correct
9 Correct 259 ms 12332 KB Output is correct
10 Correct 203 ms 12332 KB Output is correct
11 Correct 179 ms 12332 KB Output is correct
12 Correct 303 ms 12332 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 12332 KB Output is correct
2 Correct 276 ms 12332 KB Output is correct
3 Correct 266 ms 12332 KB Output is correct
4 Correct 486 ms 12332 KB Output is correct
5 Correct 476 ms 12332 KB Output is correct
6 Correct 606 ms 12332 KB Output is correct
7 Correct 579 ms 12332 KB Output is correct
8 Correct 516 ms 12332 KB Output is correct
9 Correct 666 ms 12332 KB Output is correct
10 Correct 429 ms 12332 KB Output is correct
11 Correct 286 ms 12332 KB Output is correct
12 Correct 626 ms 12332 KB Output is correct