oj.uz

Submission #910187

# Submission time Handle Problem Language Result Execution time Memory
910187 2024-01-18T01:20:33 Z LOLOLO Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 134 ms 9812 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) {
            if (k == 1)
                continue;

            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 1 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 4 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 708 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 4 ms 600 KB Output is correct
12 Correct 5 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4056 KB Output is correct
2 Correct 35 ms 4436 KB Output is correct
3 Correct 40 ms 7124 KB Output is correct
4 Correct 54 ms 9044 KB Output is correct
5 Correct 69 ms 9388 KB Output is correct
6 Correct 66 ms 9812 KB Output is correct
7 Correct 65 ms 9556 KB Output is correct
8 Correct 61 ms 9556 KB Output is correct
9 Correct 59 ms 9300 KB Output is correct
10 Correct 62 ms 9300 KB Output is correct
11 Correct 60 ms 9296 KB Output is correct
12 Correct 58 ms 9396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 860 KB Output is correct
2 Correct 16 ms 3160 KB Output is correct
3 Correct 21 ms 3420 KB Output is correct
4 Correct 28 ms 2116 KB Output is correct
5 Correct 54 ms 6880 KB Output is correct
6 Correct 54 ms 6748 KB Output is correct
7 Correct 47 ms 7248 KB Output is correct
8 Correct 55 ms 8280 KB Output is correct
9 Correct 46 ms 8012 KB Output is correct
10 Correct 48 ms 8144 KB Output is correct
11 Correct 51 ms 7976 KB Output is correct
12 Correct 50 ms 7988 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3932 KB Output is correct
2 Correct 60 ms 4064 KB Output is correct
3 Correct 66 ms 3712 KB Output is correct
4 Correct 68 ms 2736 KB Output is correct
5 Correct 88 ms 7164 KB Output is correct
6 Correct 98 ms 7184 KB Output is correct
7 Correct 88 ms 7440 KB Output is correct
8 Correct 117 ms 7568 KB Output is correct
9 Correct 98 ms 7488 KB Output is correct
10 Correct 109 ms 7620 KB Output is correct
11 Correct 108 ms 7820 KB Output is correct
12 Correct 134 ms 7612 KB Output is correct