oj.uz

Submission #1012375

# Submission time Handle Problem Language Result Execution time Memory
1012375 2024-07-02T04:58:13 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 120 ms 8024 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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 3 ms 6744 KB Output is correct
8 Correct 3 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 7508 KB Output is correct
2 Correct 30 ms 7256 KB Output is correct
3 Correct 24 ms 7516 KB Output is correct
4 Correct 31 ms 7772 KB Output is correct
5 Correct 33 ms 7864 KB Output is correct
6 Correct 34 ms 7764 KB Output is correct
7 Correct 32 ms 7732 KB Output is correct
8 Correct 33 ms 7856 KB Output is correct
9 Correct 40 ms 7772 KB Output is correct
10 Correct 34 ms 7764 KB Output is correct
11 Correct 38 ms 8024 KB Output is correct
12 Correct 34 ms 7764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6812 KB Output is correct
2 Correct 8 ms 7004 KB Output is correct
3 Correct 11 ms 7088 KB Output is correct
4 Correct 30 ms 6940 KB Output is correct
5 Correct 37 ms 7540 KB Output is correct
6 Correct 37 ms 7512 KB Output is correct
7 Correct 34 ms 7612 KB Output is correct
8 Correct 43 ms 7512 KB Output is correct
9 Correct 33 ms 7516 KB Output is correct
10 Correct 33 ms 7516 KB Output is correct
11 Correct 35 ms 7516 KB Output is correct
12 Correct 33 ms 7512 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7260 KB Output is correct
2 Correct 53 ms 7252 KB Output is correct
3 Correct 52 ms 7000 KB Output is correct
4 Correct 60 ms 7000 KB Output is correct
5 Correct 75 ms 7764 KB Output is correct
6 Correct 77 ms 7760 KB Output is correct
7 Correct 69 ms 7760 KB Output is correct
8 Correct 90 ms 7576 KB Output is correct
9 Correct 82 ms 7612 KB Output is correct
10 Correct 90 ms 7760 KB Output is correct
11 Correct 71 ms 7764 KB Output is correct
12 Correct 120 ms 7752 KB Output is correct