oj.uz

Submission #750398

# Submission time Handle Problem Language Result Execution time Memory
750398 2023-05-29T13:12:11 Z 7as__7 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7692 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define int long long
#define all(x) x.begin(),x.end()
const int sz = 1e6 + 1, mod = 1e9 + 7, inf = -1e18;
int N = 1, l, r;
int seg[(int)3e5 + 1];
void upd(int idx, int x) {
    idx--;
    idx += N;
    seg[idx] = x;
    idx /= 2;
    while (idx) {
        seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
        idx /= 2;
    }
}
int calc(int s, int e, int i) {
    if (s > r || e < l)return 0;
    if (s >= l && e <= r) {
        return seg[i];
    }
    int md = (s + e) / 2;
    return calc(s, md, i * 2) + calc(md + 1, e, i * 2 + 1);
}
signed main()
{
    int n, q, k;
    cin >> n >> q >> k;
    while (N < n)N *= 2;
    set<int>st;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        upd(i, x);
        st.insert(i);
    }
    st.insert(1e18);
    while (q--) {
        int o; cin >> o;
        if (o == 1) {
            int idx, x;
            cin >> idx >> x;
            st.insert(idx);
            upd(idx, x);
        }
        if (o == 2) {
            int ll, rr;
            cin >> ll >> rr;
            auto s = st.lower_bound(ll);
            auto e = st.upper_bound(rr);
            vector<int>v;
            while (s != e) {
                int idx = *s;
                upd(idx, seg[idx - 1 + N] / k);
                if (seg[idx - 1 + N] == 0)v.push_back(*s);
                s++;
            }
            for (auto i : v)st.erase(i);
        }
        if (o == 3) {
            cin >> l >> r;
            cout << calc(1, N, 1) << endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 10 ms 432 KB Output is correct
6 Correct 8 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 420 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 724 KB Output is correct
2 Correct 39 ms 3196 KB Output is correct
3 Correct 53 ms 3360 KB Output is correct
4 Correct 132 ms 2028 KB Output is correct
5 Correct 193 ms 6888 KB Output is correct
6 Correct 186 ms 6760 KB Output is correct
7 Execution timed out 5071 ms 6916 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 3712 KB Output is correct
2 Correct 173 ms 3744 KB Output is correct
3 Correct 173 ms 3268 KB Output is correct
4 Correct 183 ms 2596 KB Output is correct
5 Correct 253 ms 6896 KB Output is correct
6 Correct 270 ms 7056 KB Output is correct
7 Correct 256 ms 6952 KB Output is correct
8 Correct 307 ms 6984 KB Output is correct
9 Correct 282 ms 7684 KB Output is correct
10 Correct 295 ms 7252 KB Output is correct
11 Correct 254 ms 7692 KB Output is correct
12 Correct 352 ms 7368 KB Output is correct