oj.uz

Submission #31841

# Submission time Handle Problem Language Result Execution time Memory
31841 2017-09-11T03:54:25 Z Dat160601 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 703 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 && 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 6 ms 12332 KB Output is correct
3 Correct 0 ms 12332 KB Output is correct
4 Correct 6 ms 12332 KB Output is correct
5 Correct 6 ms 12332 KB Output is correct
6 Correct 16 ms 12332 KB Output is correct
7 Correct 6 ms 12332 KB Output is correct
8 Correct 9 ms 12332 KB Output is correct
9 Correct 6 ms 12332 KB Output is correct
10 Correct 13 ms 12332 KB Output is correct
11 Correct 6 ms 12332 KB Output is correct
12 Correct 6 ms 12332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 12332 KB Output is correct
2 Correct 126 ms 12332 KB Output is correct
3 Correct 159 ms 12332 KB Output is correct
4 Correct 146 ms 12332 KB Output is correct
5 Correct 229 ms 12332 KB Output is correct
6 Correct 233 ms 12332 KB Output is correct
7 Correct 263 ms 12332 KB Output is correct
8 Correct 296 ms 12332 KB Output is correct
9 Correct 263 ms 12332 KB Output is correct
10 Correct 226 ms 12332 KB Output is correct
11 Correct 229 ms 12332 KB Output is correct
12 Correct 279 ms 12332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 12332 KB Output is correct
2 Correct 69 ms 12332 KB Output is correct
3 Correct 39 ms 12332 KB Output is correct
4 Correct 189 ms 12332 KB Output is correct
5 Correct 216 ms 12332 KB Output is correct
6 Correct 296 ms 12332 KB Output is correct
7 Correct 286 ms 12332 KB Output is correct
8 Correct 249 ms 12332 KB Output is correct
9 Correct 256 ms 12332 KB Output is correct
10 Correct 263 ms 12332 KB Output is correct
11 Correct 163 ms 12332 KB Output is correct
12 Correct 193 ms 12332 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 12332 KB Output is correct
2 Correct 393 ms 12332 KB Output is correct
3 Correct 269 ms 12332 KB Output is correct
4 Correct 449 ms 12332 KB Output is correct
5 Correct 586 ms 12332 KB Output is correct
6 Correct 676 ms 12332 KB Output is correct
7 Correct 559 ms 12332 KB Output is correct
8 Correct 586 ms 12332 KB Output is correct
9 Correct 439 ms 12332 KB Output is correct
10 Correct 633 ms 12332 KB Output is correct
11 Correct 453 ms 12332 KB Output is correct
12 Correct 703 ms 12332 KB Output is correct