oj.uz

Submission #750403

# Submission time Handle Problem Language Result Execution time Memory
750403 2023-05-29T13:14:40 Z 7as__7 Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 364 ms 7736 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) {
            if (k == 1)continue;
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 3600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 764 KB Output is correct
2 Correct 40 ms 3156 KB Output is correct
3 Correct 54 ms 3300 KB Output is correct
4 Correct 133 ms 2004 KB Output is correct
5 Correct 186 ms 6856 KB Output is correct
6 Correct 201 ms 6872 KB Output is correct
7 Incorrect 121 ms 6672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 3772 KB Output is correct
2 Correct 200 ms 3744 KB Output is correct
3 Correct 197 ms 3360 KB Output is correct
4 Correct 212 ms 2612 KB Output is correct
5 Correct 315 ms 6948 KB Output is correct
6 Correct 299 ms 6912 KB Output is correct
7 Correct 257 ms 7048 KB Output is correct
8 Correct 330 ms 7000 KB Output is correct
9 Correct 283 ms 7736 KB Output is correct
10 Correct 293 ms 7356 KB Output is correct
11 Correct 251 ms 7700 KB Output is correct
12 Correct 364 ms 7292 KB Output is correct