Submission #750404

#	Time	Username	Problem	Language	Result	Execution time	Memory
750404		7as__7	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	348 ms	7712 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75