oj.uz

Submission #828576

# Submission time Handle Problem Language Result Execution time Memory
828576 2023-08-17T11:38:23 Z AlphaMale06 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 221 ms 8128 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 556 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 556 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5040 KB Output is correct
2 Correct 33 ms 4608 KB Output is correct
3 Correct 33 ms 6964 KB Output is correct
4 Correct 39 ms 7680 KB Output is correct
5 Correct 65 ms 8036 KB Output is correct
6 Correct 49 ms 8128 KB Output is correct
7 Correct 45 ms 8012 KB Output is correct
8 Correct 45 ms 8112 KB Output is correct
9 Correct 42 ms 7916 KB Output is correct
10 Correct 45 ms 7892 KB Output is correct
11 Correct 41 ms 7884 KB Output is correct
12 Correct 41 ms 7928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1108 KB Output is correct
2 Correct 11 ms 2900 KB Output is correct
3 Correct 20 ms 3156 KB Output is correct
4 Correct 43 ms 2716 KB Output is correct
5 Correct 54 ms 6640 KB Output is correct
6 Correct 58 ms 6636 KB Output is correct
7 Correct 39 ms 6732 KB Output is correct
8 Correct 54 ms 6612 KB Output is correct
9 Correct 54 ms 6536 KB Output is correct
10 Correct 58 ms 6632 KB Output is correct
11 Correct 51 ms 6536 KB Output is correct
12 Correct 52 ms 6512 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4552 KB Output is correct
2 Correct 80 ms 4628 KB Output is correct
3 Correct 95 ms 4004 KB Output is correct
4 Correct 120 ms 3680 KB Output is correct
5 Correct 116 ms 7920 KB Output is correct
6 Correct 132 ms 7848 KB Output is correct
7 Correct 112 ms 7920 KB Output is correct
8 Correct 171 ms 7964 KB Output is correct
9 Correct 141 ms 7756 KB Output is correct
10 Correct 162 ms 7800 KB Output is correct
11 Correct 121 ms 7800 KB Output is correct
12 Correct 221 ms 7784 KB Output is correct