oj.uz

Submission #750572

# Submission time Handle Problem Language Result Execution time Memory
750572 2023-05-29T18:17:17 Z MuntherCarrot Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 141 ms 5920 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 5488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1040 KB Output is correct
2 Correct 19 ms 2132 KB Output is correct
3 Correct 24 ms 2268 KB Output is correct
4 Correct 40 ms 2384 KB Output is correct
5 Correct 62 ms 5272 KB Output is correct
6 Correct 61 ms 5268 KB Output is correct
7 Correct 58 ms 5920 KB Output is correct
8 Correct 62 ms 5324 KB Output is correct
9 Correct 65 ms 5156 KB Output is correct
10 Correct 64 ms 5140 KB Output is correct
11 Correct 68 ms 5156 KB Output is correct
12 Correct 60 ms 5132 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -