oj.uz

Submission #916793

# Submission time Handle Problem Language Result Execution time Memory
916793 2024-01-26T14:23:21 Z Dec0Dedd Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 100 ms 9040 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

struct fenwick {
    vector<ll> bit;
    int n;
 
    void init(int sz) {
        n=sz+10;
        bit.assign(n, 0);
    }
 
    ll sum(int r) {
        ll res=0;
        for (;r>=0; r=(r&(r+1))-1) res+=bit[r];
        return res;
    }
 
    ll que(int l, int r) {
        return sum(r)-sum(l-1);
    }
 
    void upd(int x, ll d) {
        for (; x<n; x=x|(x+1)) bit[x]+=d;
    }

    void st(int x, ll d) {
        ll vl=que(x, x);
        upd(x, d-vl);
    }
};

const int N = 1e5+10;

int n, q, k, c[N];

void solve() {
    cin>>n>>q>>k;
    for (int i=1; i<=n; ++i) cin>>c[i];

    fenwick f; f.init(n+10);

    set<int> st;
    for (int i=1; i<=n; ++i) {
        f.st(i, c[i]);
        if (c[i] > 0) st.insert(i);
    }

    while (q--) {
        int s, t, u; cin>>s>>t>>u;
        if (s == 1) {
            f.upd(t, u-c[t]);
            c[t]=u;
            if (u > 0) st.insert(t);
        } else if (s == 2) {
            auto ptr=st.lower_bound(t);
            if (k == 1) continue;

            while (ptr != st.end()) {
                if ((*ptr) > u) break;
                int nvl=c[*ptr]/k;
                f.upd(*ptr, nvl-c[*ptr]);
                c[*ptr]=nvl;
                
                if (nvl == 0) {
                    st.erase(ptr++);
                    continue;
                } ++ptr;
            }
        } else cout<<f.que(t, u)<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 712 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3664 KB Output is correct
2 Correct 36 ms 2768 KB Output is correct
3 Correct 41 ms 5284 KB Output is correct
4 Correct 52 ms 6616 KB Output is correct
5 Correct 60 ms 6740 KB Output is correct
6 Correct 60 ms 6576 KB Output is correct
7 Correct 65 ms 6672 KB Output is correct
8 Correct 67 ms 6616 KB Output is correct
9 Correct 53 ms 6736 KB Output is correct
10 Correct 53 ms 6672 KB Output is correct
11 Correct 53 ms 6728 KB Output is correct
12 Correct 53 ms 6952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 11 ms 1884 KB Output is correct
3 Correct 13 ms 2008 KB Output is correct
4 Correct 24 ms 1372 KB Output is correct
5 Correct 65 ms 4436 KB Output is correct
6 Correct 38 ms 3932 KB Output is correct
7 Correct 48 ms 4436 KB Output is correct
8 Correct 38 ms 3932 KB Output is correct
9 Correct 35 ms 3992 KB Output is correct
10 Correct 35 ms 3932 KB Output is correct
11 Correct 36 ms 3932 KB Output is correct
12 Correct 36 ms 3908 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3420 KB Output is correct
2 Correct 45 ms 5264 KB Output is correct
3 Correct 50 ms 4236 KB Output is correct
4 Correct 53 ms 4180 KB Output is correct
5 Correct 72 ms 8992 KB Output is correct
6 Correct 81 ms 9012 KB Output is correct
7 Correct 75 ms 8928 KB Output is correct
8 Correct 99 ms 9040 KB Output is correct
9 Correct 76 ms 8788 KB Output is correct
10 Correct 84 ms 8768 KB Output is correct
11 Correct 70 ms 8784 KB Output is correct
12 Correct 100 ms 8788 KB Output is correct