oj.uz

Submission #910185

# Submission time Handle Problem Language Result Execution time Memory
910185 2024-01-18T01:15:40 Z LOLOLO Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9904 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]);
            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 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 772 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 604 KB Output is correct
11 Correct 3 ms 752 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1372 KB Output is correct
2 Correct 16 ms 3420 KB Output is correct
3 Correct 18 ms 3676 KB Output is correct
4 Correct 31 ms 3256 KB Output is correct
5 Correct 52 ms 8160 KB Output is correct
6 Correct 50 ms 8276 KB Output is correct
7 Execution timed out 5035 ms 8352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5408 KB Output is correct
2 Correct 56 ms 5708 KB Output is correct
3 Correct 65 ms 4680 KB Output is correct
4 Correct 61 ms 4528 KB Output is correct
5 Correct 90 ms 9512 KB Output is correct
6 Correct 97 ms 9672 KB Output is correct
7 Correct 86 ms 9904 KB Output is correct
8 Correct 112 ms 9648 KB Output is correct
9 Correct 101 ms 9340 KB Output is correct
10 Correct 110 ms 9644 KB Output is correct
11 Correct 89 ms 9280 KB Output is correct
12 Correct 136 ms 9760 KB Output is correct