Submission #31840

#	Time	Username	Problem	Language	Result	Execution time	Memory
31840		Kanvie	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	746 ms	9048 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,kk,q,x,y,z,mx[400001];
long long f[400001],a[100001];
void init(int k, int l, int r)
{
    if(r<l)return;
    if(l==r)
    {
        f[k]=a[l];
        mx[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(2*k,l,mid);
    init(2*k+1,mid+1,r);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
void dolazy(int k,int l, int r)
{
    if(l!=r&&mx[k]==0)
    {
        mx[2*k]=0;
        mx[2*k+1]=0;
        f[2*k]=0;
        f[2*k+1]=0;
    }
    return;
}
void upd(int k, int l, int r, int p, int gt)
{
    dolazy(k,l,r);
    if(p<l||p>r||l>r)return;
    if(l==r)
    {
        f[k]=gt;
        mx[k]=gt;
        return;
    }
    int mid=(l+r)/2;
    upd(2*k,l,mid,p,gt);
    upd(2*k+1,mid+1,r,p,gt);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
void chg(int k, int l, int r, int L, int R)
{
    if(kk==1)return;
    dolazy(k,l,r);
    if(R<l||L>r||l>r)return;
    if(L<=l&&r<=R&&mx[k]<kk)
    {
        f[k]=0;
        mx[k]=0;
        return;
    }
    if(l==r)
    {
        f[k]/=kk;
        mx[k]=f[k];
        return;
    }
    int mid=(l+r)/2;
    chg(2*k,l,mid,L,R);
    chg(2*k+1,mid+1,r,L,R);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
long long gets(int k, int l, int r, int L, int R)
{
    dolazy(k,l,r);
    if(R<l||L>r||l>r)return 0;
    if(L<=l&&r<=R)return f[k];
    int mid=(l+r)/2;
    return gets(2*k,l,mid,L,R)+gets(2*k+1,mid+1,r,L,R);
}
signed main()
{
    cin>>n>>q>>kk;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    init(1,1,n);
    while(q--)
    {
        cin>>x>>y>>z;
        if(x==1)
            upd(1,1,n,y,z);
        else
        {
            if(x==2)
                chg(1,1,n,y,z);
            else
                cout<<gets(1,1,n,y,z)<<"\n";
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75