Submission #750396

#	Time	Username	Problem	Language	Result	Execution time	Memory
750396		7as__7	Sterilizing Spray (JOI15_sterilizing)	C++17	0 / 100	5069 ms	6184 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 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;
        }
    }
}

Compilation message (stderr)

sterilizing.cpp:8:46: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
    8 | const int sz = 1e6 + 1, mod = 1e9 + 7, inf = -1e18;
      |                                              ^~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:41:15: warning: overflow in conversion from 'double' to 'std::set<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   41 |     st.insert(1e18);
      |               ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75