Submission #1012374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012374		DucNguyen2007	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	101 ms	10408 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
ll n,q,a[maxN+1],k;
struct segment
{
    struct Node
    {
        ll s,mx;
        Node()
        {
            s=0;
            mx=-inf;
        }
        Node(ll S,ll mxn)
        {
            s=S;
            mx=mxn;
        }
    }sum[4*maxN+1];
    Node meg(Node x,Node y)
    {
        Node res;
        res.s=x.s+y.s;
        res.mx=max(x.mx,y.mx);
        return res;
    }
    void Build(int x,int low,int high)
    {
        if(low==high)
        {
            sum[x]=Node(a[low],a[low]);
            return;
        }
        int mid=(low+high)/2;
        Build(2*x,low,mid);
        Build(2*x+1,mid+1,high);
        sum[x]=meg(sum[2*x],sum[2*x+1]);
    }
    ll pos,val,l,r;
    void Set(int x,int low,int high)
    {
        if(low==high)
        {
            sum[x]=Node(val,val);
            return;
        }
        int mid=(low+high)/2;
        if(pos<=mid)
        {
            Set(2*x,low,mid);
        }
        else Set(2*x+1,mid+1,high);
        sum[x]=meg(sum[2*x],sum[2*x+1]);
    }
    void set_val(ll pos,ll val)
    {
        this->pos=pos;
        this->val=val;
        Set(1,1,n);
    }
    void Update(int x,int low,int high)
    {
        if(low>r||high<l||sum[x].mx==0)
        {
            return;
        }
        if(low==high)
        {
            sum[x].s/=k;
            sum[x].mx/=k;
            return;
        }
        int mid=(low+high)/2;
        Update(2*x,low,mid);
        Update(2*x+1,mid+1,high);
        sum[x]=meg(sum[2*x],sum[2*x+1]);
    }
    void update_val(ll l,ll r)
    {
        this->l=l;
        this->r=r;
        Update(1,1,n);
    }
    Node get(int x,int low,int high)
    {
        if(low>r||high<l)
        {
            return Node(0,-inf);
        }
        if(low>=l&&high<=r)
        {
            return sum[x];
        }
        int mid=(low+high)/2;
        Node get1=get(2*x,low,mid);
        Node get2=get(2*x+1,mid+1,high);
        return meg(get1,get2);
    }
    Node query(ll l,ll r)
    {
        this->l=l;
        this->r=r;
        return get(1,1,n);
    }
}st;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    st.Build(1,1,n);
    while(q--)
    {
        ll s;
        cin>>s;
        if(s==1)
        {
            ll pos,val;
            cin>>pos>>val;
            st.set_val(pos,val);
        }
        else if(s==2)
        {
            ll l,r;
            cin>>l>>r;
            if(k>1)
            {
                st.update_val(l,r);
            }
        }
        else
        {
            ll l,r;
            cin>>l>>r;
            cout<<st.query(l,r).s<<'\n';
        }
    }
}

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