Submission #828576

#	Time	Username	Problem	Language	Result	Execution time	Memory
828576		AlphaMale06	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	221 ms	8128 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int k;
const int N = 100005;

ll st[4*N][2];
ll a[N];

void Build(int node, int l, int r){
    if(l>r)return;
    if(l==r){
        st[node][0]=a[l]; st[node][1]=a[l];
        return;
    }
    int mid=(l+r)/2;
    Build(2*node+1, l, mid);
    Build(2*node+2, mid+1, r);
    st[node][0]=st[2*node+1][0]+st[2*node+2][0];
    st[node][1]=max(st[2*node+1][1], st[2*node+2][1]);
}

void Update(int node, int l, int r, int ind, int val){
    if(l>r || l >ind || r<ind)return;
    if(l==r){
        st[node][0]=val;
        st[node][1]=val;
        return;
    }
    int mid=(l+r)/2;
    Update(2*node+1, l, mid, ind, val);
    Update(2*node+2, mid+1, r, ind, val);
    st[node][0]=st[2*node+1][0]+st[2*node+2][0];
    st[node][1]=max(st[2*node+1][1], st[2*node+2][1]);
}

ll Get(int node, int l, int r, int L, int R){
    if(l>r || l>R || r<L)return 0;
    if(L<=l && R>=r)return st[node][0];
    int mid=(l+r)/2;
    return Get(2*node+1, l, mid, L, R)+Get(2*node+2, mid+1, r, L, R);
}

void Spray(int node, int l, int r, int L, int R){
    if(l>r || l>R || r<L)return;
    if(L<=l && R>=r){
        if(l==r){
            st[node][0]/=k;
            st[node][1]/=k;
            return;
        }
        if(st[node][1]>0){
            int mid=(l+r)/2;
            Spray(2*node+1, l, mid, L, R);
            Spray(2*node+2, mid+1, r, L, R);
            st[node][0]=st[2*node+1][0]+st[2*node+2][0];
            st[node][1]=max(st[2*node+1][1], st[2*node+2][1]);
        }
        return;
    }
    int mid = (l+r)/2;
    Spray(2*node+1, l, mid, L, R);
    Spray(2*node+2, mid+1, r, L, R);
    st[node][0]=st[2*node+1][0]+st[2*node+2][0];
    st[node][1]=max(st[2*node+1][1], st[2*node+2][1]);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q >> k;
    for(int i=0; i< n; i++)cin >> a[i];
    Build(0, 0, n-1);
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int ind, val;
            cin >> ind >> val;
            Update(0, 0, n-1, ind-1, val);
        }
        if(t==2){
            int l, r;
            cin >> l >> r;
            if(k!=1){
                Spray(0, 0, n-1, l-1, r-1);
            }
        }
        if(t==3){
            int l, r;
            cin >> l >> r;
            cout << Get(0, 0, n-1, l-1, r-1) << '\n';
        }
    }
}

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