oj.uz

Submission #1110427

# Submission time Handle Problem Language Result Execution time Memory
1110427 2024-11-09T12:15:29 Z vladilius Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 341 ms 11740 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    vector<ll> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] = x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v] = t[vv] + t[vv + 1];
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
    }
    ll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return get(vv, tl, tm, l, r) + get(vv + 1, tm + 1, tr, l, r);
    }
    ll get(int l, int r){
        return get(1, 1, n, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q, k; cin>>n>>q>>k;
    vector<int> a(n + 1);
    ST T(n);
    set<int> st;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        T.upd(i, a[i]);
        if (a[i]){
            st.insert(i);
        }
    }
    vector<int> all;
    while (q--){
        int s, x, y; cin>>s>>x>>y;
        if (s == 1){
            T.upd(x, y);
            auto it = st.find(x);
            if (it != st.end()){
                st.erase(it);
            }
            if (y) st.insert(x);
            a[x] = y;
        }
        else if (s == 2){
            if (k == 1) continue;
            auto it = st.lower_bound(x);
            all.clear();
            while (it != st.end() && (*it) <= y){
                all.pb((*it));
                it++;
            }
            for (int j: all){
                a[j] /= k;
                T.upd(j, a[j]);
                if (!a[j]){
                    st.erase(j);
                }
            }
        }
        else {
            cout<<T.get(x, y)<<"\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 544 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 4 ms 652 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 6 ms 592 KB Output is correct
10 Correct 5 ms 592 KB Output is correct
11 Correct 6 ms 760 KB Output is correct
12 Correct 5 ms 592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 6752 KB Output is correct
2 Correct 48 ms 5216 KB Output is correct
3 Correct 62 ms 8524 KB Output is correct
4 Correct 70 ms 10924 KB Output is correct
5 Correct 77 ms 11572 KB Output is correct
6 Correct 88 ms 11592 KB Output is correct
7 Correct 75 ms 11592 KB Output is correct
8 Correct 87 ms 11424 KB Output is correct
9 Correct 70 ms 11336 KB Output is correct
10 Correct 72 ms 11336 KB Output is correct
11 Correct 72 ms 11336 KB Output is correct
12 Correct 70 ms 11252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1104 KB Output is correct
2 Correct 17 ms 3152 KB Output is correct
3 Correct 21 ms 3524 KB Output is correct
4 Correct 38 ms 3152 KB Output is correct
5 Correct 59 ms 7752 KB Output is correct
6 Correct 64 ms 7752 KB Output is correct
7 Correct 61 ms 7800 KB Output is correct
8 Correct 71 ms 7656 KB Output is correct
9 Correct 57 ms 7916 KB Output is correct
10 Correct 61 ms 7880 KB Output is correct
11 Correct 57 ms 7876 KB Output is correct
12 Correct 69 ms 7888 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 6612 KB Output is correct
2 Correct 100 ms 6728 KB Output is correct
3 Correct 155 ms 5560 KB Output is correct
4 Correct 123 ms 5192 KB Output is correct
5 Correct 165 ms 11716 KB Output is correct
6 Correct 197 ms 11716 KB Output is correct
7 Correct 187 ms 11712 KB Output is correct
8 Correct 241 ms 11740 KB Output is correct
9 Correct 200 ms 11712 KB Output is correct
10 Correct 251 ms 11720 KB Output is correct
11 Correct 176 ms 11712 KB Output is correct
12 Correct 341 ms 11740 KB Output is correct