oj.uz

Submission #750394

# Submission time Handle Problem Language Result Execution time Memory
750394 2023-05-29T13:08:13 Z 7as__7 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7720 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#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 5 ms 212 KB Output is correct
2 Correct 6 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 8 ms 468 KB Output is correct
6 Correct 8 ms 516 KB Output is correct
7 Correct 8 ms 508 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 8 ms 472 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 760 KB Output is correct
2 Correct 42 ms 3180 KB Output is correct
3 Correct 52 ms 3276 KB Output is correct
4 Correct 141 ms 2088 KB Output is correct
5 Correct 219 ms 6928 KB Output is correct
6 Correct 177 ms 6704 KB Output is correct
7 Execution timed out 5032 ms 6904 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3788 KB Output is correct
2 Correct 168 ms 3788 KB Output is correct
3 Correct 171 ms 3280 KB Output is correct
4 Correct 221 ms 2656 KB Output is correct
5 Correct 254 ms 6964 KB Output is correct
6 Correct 307 ms 6956 KB Output is correct
7 Correct 255 ms 6872 KB Output is correct
8 Correct 313 ms 6980 KB Output is correct
9 Correct 266 ms 7720 KB Output is correct
10 Correct 288 ms 7320 KB Output is correct
11 Correct 300 ms 7692 KB Output is correct
12 Correct 368 ms 7412 KB Output is correct