Submission #555940

#	Time	Username	Problem	Language	Result	Execution time	Memory
555940		status_coding	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	245 ms	9484 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

struct segS
{
    long long sum, maxi;
};

long long n,k,q;
vector<segS> seg;

void upd(int i, int st, int dr, int p, long long val)
{
    if(st == dr)
    {
        seg[p].sum = seg[p].maxi = val;
        return;
    }

    int mij =  (st+dr)/2;

    if(i <= mij)
        upd(i, st, mij, 2*p, val);
    else
        upd(i, mij+1, dr, 2*p+1, val);

    seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
    seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}

void imp(int stt, int drt, int st, int dr, int p)
{
    if(st == dr)
    {
        seg[p].sum /= k;
        seg[p].maxi /= k;
        return;
    }

    int mij = (st+dr)/2;

    if(stt <= st && dr <= drt)
    {
        if(seg[2*p].maxi > 0)
            imp(stt, drt, st, mij, 2*p);

        if(seg[2*p+1].maxi > 0)
            imp(stt, drt, mij+1, dr, 2*p+1);
    }
    else
    {
        if(drt <= mij)
            imp(stt, drt, st, mij, 2*p);
        else if(stt > mij)
            imp(stt, drt, mij+1, dr, 2*p+1);
        else
        {
            imp(stt, mij, st, mij, 2*p);
            imp(mij+1, drt, mij+1, dr, 2*p+1);
        }
    }

    seg[p].sum = seg[2*p].sum + seg[2*p+1].sum;
    seg[p].maxi = max(seg[2*p].maxi, seg[2*p+1].maxi);
}

long long query(int stt, int drt, int st, int dr, int p)
{
    if(stt == st && drt == dr)
        return seg[p].sum;

    int mij = (st+dr)/2;

    if(drt <= mij)
        return query(stt, drt, st, mij, 2*p);
    else if(stt > mij)
        return query(stt, drt, mij+1, dr, 2*p+1);
    else
        return query(stt, mij, st, mij, 2*p) + query(mij+1, drt, mij+1, dr, 2*p+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>q>>k;
    seg.resize(4*n+4);

    for(int i=1;i<=n;i++)
    {
       long long x;
       cin>>x;

       upd(i, 1, n, 1, x);
    }

    while(q)
    {
        q--;

        int tip;
        cin>>tip;

        if(tip == 1)
        {
            long long i, val;
            cin>>i>>val;

            upd(i, 1, n, 1, val);
        }

        if(tip == 2)
        {
            int l, r;
            cin>>l>>r;

            if(k > 1)
                imp(l, r, 1, n, 1);
        }

        if(tip == 3)
        {
            int l, r;
            cin>>l>>r;

            cout<<query(l, r, 1, n, 1)<<'\n';
        }
    }
    return 0;
}

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