Submission #31838

#	Time	Username	Problem	Language	Result	Execution time	Memory
31838		Dat160601	Sterilizing Spray (JOI15_sterilizing)	C++14	90 / 100	666 ms	12332 KiB

sterilizing

#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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75