oj.uz

Submission #750404

# Submission time Handle Problem Language Result Execution time Memory
750404 2023-05-29T13:15:11 Z 7as__7 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 348 ms 7712 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);
}
inline int read()
{
    int x = 0; char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}
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;
            if (k == 1)continue;
            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 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 8 ms 520 KB Output is correct
6 Correct 7 ms 508 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 3772 KB Output is correct
2 Correct 130 ms 2792 KB Output is correct
3 Correct 133 ms 5332 KB Output is correct
4 Correct 174 ms 6752 KB Output is correct
5 Correct 204 ms 7004 KB Output is correct
6 Correct 193 ms 7052 KB Output is correct
7 Correct 193 ms 7000 KB Output is correct
8 Correct 191 ms 6988 KB Output is correct
9 Correct 180 ms 7000 KB Output is correct
10 Correct 220 ms 7032 KB Output is correct
11 Correct 195 ms 6984 KB Output is correct
12 Correct 190 ms 7060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 772 KB Output is correct
2 Correct 42 ms 3224 KB Output is correct
3 Correct 54 ms 3284 KB Output is correct
4 Correct 131 ms 1992 KB Output is correct
5 Correct 173 ms 6860 KB Output is correct
6 Correct 183 ms 6728 KB Output is correct
7 Correct 165 ms 6716 KB Output is correct
8 Correct 175 ms 6996 KB Output is correct
9 Correct 157 ms 7708 KB Output is correct
10 Correct 155 ms 7684 KB Output is correct
11 Correct 154 ms 7624 KB Output is correct
12 Correct 166 ms 7712 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3772 KB Output is correct
2 Correct 171 ms 3824 KB Output is correct
3 Correct 167 ms 3288 KB Output is correct
4 Correct 181 ms 2608 KB Output is correct
5 Correct 262 ms 7032 KB Output is correct
6 Correct 279 ms 6908 KB Output is correct
7 Correct 254 ms 6948 KB Output is correct
8 Correct 311 ms 6976 KB Output is correct
9 Correct 267 ms 7696 KB Output is correct
10 Correct 284 ms 7328 KB Output is correct
11 Correct 260 ms 7660 KB Output is correct
12 Correct 348 ms 7416 KB Output is correct