oj.uz

Submission #1012374

# Submission time Handle Problem Language Result Execution time Memory
1012374 2024-07-02T04:57:37 Z DucNguyen2007 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 101 ms 10408 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7148 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 2 ms 6860 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9296 KB Output is correct
2 Correct 27 ms 8788 KB Output is correct
3 Correct 29 ms 9040 KB Output is correct
4 Correct 31 ms 9812 KB Output is correct
5 Correct 37 ms 10324 KB Output is correct
6 Correct 40 ms 10408 KB Output is correct
7 Correct 38 ms 10348 KB Output is correct
8 Correct 38 ms 10320 KB Output is correct
9 Correct 34 ms 10068 KB Output is correct
10 Correct 35 ms 10120 KB Output is correct
11 Correct 36 ms 10064 KB Output is correct
12 Correct 36 ms 10064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7252 KB Output is correct
2 Correct 9 ms 7260 KB Output is correct
3 Correct 11 ms 7316 KB Output is correct
4 Correct 31 ms 8104 KB Output is correct
5 Correct 38 ms 8788 KB Output is correct
6 Correct 37 ms 8796 KB Output is correct
7 Correct 34 ms 9072 KB Output is correct
8 Correct 38 ms 8776 KB Output is correct
9 Correct 32 ms 8816 KB Output is correct
10 Correct 34 ms 8788 KB Output is correct
11 Correct 33 ms 8660 KB Output is correct
12 Correct 34 ms 8788 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8808 KB Output is correct
2 Correct 51 ms 8788 KB Output is correct
3 Correct 50 ms 8276 KB Output is correct
4 Correct 63 ms 8692 KB Output is correct
5 Correct 72 ms 10068 KB Output is correct
6 Correct 78 ms 10068 KB Output is correct
7 Correct 68 ms 10068 KB Output is correct
8 Correct 88 ms 10064 KB Output is correct
9 Correct 81 ms 10068 KB Output is correct
10 Correct 87 ms 10016 KB Output is correct
11 Correct 70 ms 10064 KB Output is correct
12 Correct 101 ms 9904 KB Output is correct