oj.uz

Submission #750574

# Submission time Handle Problem Language Result Execution time Memory
750574 2023-05-29T18:17:43 Z MuntherCarrot Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 445 ms 9292 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define endl '\n'


#define all(x) x.begin(),x.end()
const ll MOD = 1e9 + 7, SZ = 1e5 + 10, INF = 1e18;
int N = 1 << 18, t[1 << 19];
void upd(int i, int v){
    i += N;
    t[i] = v;
    for(i/=2;i;i/=2)
        t[i] = t[i * 2] + t[i * 2 + 1];
}
int clc(int l, int r, int i = 1, int from = 1, int to = N){
    if(from > r || to < l)
        return 0;
    if(from >= l && to <= r)
        return t[i];
    int mid = (from + to)/2;
    return clc(l, r, i*2, from, mid) + clc(l, r, i*2 + 1, mid + 1, to);
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q, k;
    cin >> n >> q >> k;
    int arr[n];
    set<int> st;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        upd(i, arr[i]);
        if(arr[i])
            st.insert(i + 1);
    }
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1){
            arr[l - 1] = r;
            upd(l - 1, r);
            if(r)
                st.insert(l);
        }
        else if(t == 3)
            cout << clc(l, r) << endl;
        else if(k != 1){
            while(l <= r){
                auto x = st.lower_bound(l);
                if(x == st.end() || *x > r)
                    break;
                arr[*x - 1] /= k;
                upd(*x - 1, arr[*x - 1]);
                if(arr[*x - 1] == 0)
                    st.erase(*x);
                l = *x + 1;
            }
        }
    }
    return 0;
}

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 3 ms 468 KB Output is correct
4 Correct 6 ms 516 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4144 KB Output is correct
2 Correct 56 ms 4680 KB Output is correct
3 Correct 57 ms 7628 KB Output is correct
4 Correct 86 ms 9044 KB Output is correct
5 Correct 88 ms 9240 KB Output is correct
6 Correct 83 ms 9164 KB Output is correct
7 Correct 84 ms 9264 KB Output is correct
8 Correct 88 ms 9196 KB Output is correct
9 Correct 93 ms 9192 KB Output is correct
10 Correct 95 ms 9252 KB Output is correct
11 Correct 110 ms 9284 KB Output is correct
12 Correct 82 ms 9292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 668 KB Output is correct
2 Correct 16 ms 2356 KB Output is correct
3 Correct 19 ms 2400 KB Output is correct
4 Correct 39 ms 1552 KB Output is correct
5 Correct 62 ms 5080 KB Output is correct
6 Correct 59 ms 5096 KB Output is correct
7 Correct 74 ms 5472 KB Output is correct
8 Correct 68 ms 5068 KB Output is correct
9 Correct 57 ms 5060 KB Output is correct
10 Correct 56 ms 5052 KB Output is correct
11 Correct 56 ms 5168 KB Output is correct
12 Correct 54 ms 5044 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4100 KB Output is correct
2 Correct 104 ms 5596 KB Output is correct
3 Correct 181 ms 4740 KB Output is correct
4 Correct 123 ms 4376 KB Output is correct
5 Correct 189 ms 8968 KB Output is correct
6 Correct 225 ms 9152 KB Output is correct
7 Correct 191 ms 9048 KB Output is correct
8 Correct 303 ms 9016 KB Output is correct
9 Correct 253 ms 9120 KB Output is correct
10 Correct 298 ms 9068 KB Output is correct
11 Correct 207 ms 9024 KB Output is correct
12 Correct 445 ms 9104 KB Output is correct