oj.uz

Submission #910186

# Submission time Handle Problem Language Result Execution time Memory
910186 2024-01-18T01:17:58 Z LOLOLO Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7884 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 100;

ll f[N];
void upd(int i, ll x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

ll get(int i) {
    ll s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;
}

ll c[N];
ll solve() {
    int n, q, k;
    cin >> n >> q >> k;

    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        upd(i, c[i]);
    }

    set <int> st;
    for (int i = 1; i <= n; i++)
        st.insert(i);

    while (q--) {
        int s, l, r;
        cin >> s >> l >> r;

        if (s == 1) {
            upd(l, r - c[l]);
            if (c[l])
                st.erase(l);

            c[l] = r;
            if (r) {
                st.insert(l);
            }
        }

        if (s == 2) {
            vector <int> v;
            auto it = st.lower_bound(l);
            while (it != st.end()) {
                if (*it > r)
                    break;

                v.pb(*it);
                it = next(it);
            }

            for (auto x : v) {
                upd(x, (c[x] / k) - c[x]);
                c[x] /= k;
                if (c[x] == 0)
                    st.erase(x);
            }
        }

        if (s == 3) {
            cout << get(r) - get(l - 1) << '\n';
        }
    }

    return 0;
}

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

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 4312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 940 KB Output is correct
2 Correct 17 ms 3336 KB Output is correct
3 Correct 18 ms 3404 KB Output is correct
4 Correct 28 ms 2140 KB Output is correct
5 Correct 52 ms 6848 KB Output is correct
6 Correct 51 ms 6748 KB Output is correct
7 Execution timed out 5036 ms 7496 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4044 KB Output is correct
2 Correct 64 ms 3976 KB Output is correct
3 Correct 65 ms 3712 KB Output is correct
4 Correct 61 ms 2712 KB Output is correct
5 Correct 90 ms 7168 KB Output is correct
6 Correct 97 ms 7180 KB Output is correct
7 Correct 85 ms 7420 KB Output is correct
8 Correct 112 ms 7580 KB Output is correct
9 Correct 103 ms 7516 KB Output is correct
10 Correct 110 ms 7492 KB Output is correct
11 Correct 89 ms 7520 KB Output is correct
12 Correct 164 ms 7884 KB Output is correct