Submission #1275199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275199		MunkhErdene	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5093 ms	40928 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define lll __int128
#define ll long long
const ll mod = 1e9 + 7;
const ll mod1 = 998244353;
const ll naim = 1e9;
const ll max_bit = 60;
const ull tom = ULLONG_MAX;
const ll MAXN = 100005;
const ll LOG = 20;
const ll NAIM = 1e18;
const ll N = 2e6 + 5;
int main() {
    #define pb push_back
    #define ff first
    #define ss second
    #define _ << " " <<
    #define yes cout<<"YES\n"
    #define no cout<<"NO\n"
    #define all(x) x.begin(),x.end()
    #define rall(x) x.rbegin(),x.rend()
    #define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define FOR(i, a, b) for (ll i = (a); i < (b); i++)
    #define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
    // ---------- GCD ----------
    auto gcd = [&](ll a, ll b) {
        while (b) {
            a %= b;
            swap(a, b);
        }
        return a;
    };
    // ---------- LCM ----------
    auto lcm = [&](ll a, ll b) {
        return a / gcd(a, b) * b;
    };
    // ---------- Modular Exponentiation ----------
    function<ll(ll, ll, ll)> modpow = [&](ll a, ll b, ll m) {
        ll c = 1;
        a %= m;
        while (b > 0) {
            if (b & 1) c = c * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return c;
    };
    // ---------- Modular Inverse (Fermat’s Little Theorem) ----------
    function<ll(ll, ll)> modinv = [&](ll a, ll m) {
        return modpow(a, m - 2, m);
    };
    // ---------- Factorials and Inverse Factorials ----------
    vector<ll> fact(N), invfact(N);
    auto pre_fact = [&](ll n = N-1, ll m = mod) {
        fact[0] = 1;
        for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * i % m;
        invfact[n] = modinv(fact[n], m);
        for (ll i = n; i > 0; i--) invfact[i-1] = invfact[i] * i % m;
    };
    // ---------- nCr ----------
    auto nCr = [&](ll n, ll r, ll m = mod) {
        if (r < 0 || r > n) return 0LL;
        return fact[n] * invfact[r] % m * invfact[n-r] % m;
    };
    // ---------- Sieve of Eratosthenes ----------
    vector<ll> primes;
    vector<bool> is_prime(N);
    auto sieve = [&](ll n = N-1) {
        fill(is_prime.begin(), is_prime.begin() + n + 1, true);
        is_prime[0] = is_prime[1] = false;
        for (ll i = 2; i * i <= n; i++) {
            if (is_prime[i]) {
                for (ll j = i * i; j <= n; j += i)
                    is_prime[j] = false;
            }
        }
        for (ll i = 2; i <= n; i++)
            if (is_prime[i]) primes.pb(i);
    };
    function<void()> solve = [&]() {
        ll n, q, k; cin >> n >> q >> k;
        struct SegTree {
            vector<ll> sum;
            ll n;
            SegTree(ll _n = 0) { init(_n); }
            void init(ll _n) {
                n = _n;
                if (n > 0) sum.assign(4 * n + 5, 0);
            }

        private:
            void build(ll v, ll l, ll r, vector<ll> &a) {
                if (l == r) {
                    sum[v] = a[l];
                    return;
                }
                ll m = (l + r) >> 1;
                build(v << 1, l, m, a);
                build(v << 1 | 1, m + 1, r, a);
                sum[v] = sum[v << 1] + sum[v << 1 | 1];
            }

            void updateSet(ll v, ll l, ll r, ll pos, ll val) {
                if (l == r) {
                    sum[v] = val;
                    return;
                }
                ll m = (l + r) >> 1;
                if (pos <= m) updateSet(v << 1, l, m, pos, val);
                else updateSet(v << 1 | 1, m + 1, r, pos, val);
                sum[v] = sum[v << 1] + sum[v << 1 | 1];
            }

            void updateDiv(ll v, ll l, ll r, ll pos, ll k) {
                if (l == r) {
                    sum[v] /= k;
                    return;
                }
                ll m = (l + r) >> 1;
                if (pos <= m) updateDiv(v << 1, l, m, pos, k);
                else updateDiv(v << 1 | 1, m + 1, r, pos, k);
                sum[v] = sum[v << 1] + sum[v << 1 | 1];
            }

            ll querySum(ll v, ll l, ll r, ll ql, ll qr) {
                if (r < ql || l > qr) return 0;
                if (ql <= l && r <= qr) return sum[v];
                int m = (l + r) >> 1;
                return querySum(v << 1, l, m, ql, qr) + querySum(v << 1 | 1, m + 1, r, ql, qr);
            }

        public:
            void build(vector<ll> &a) {
                if (n <= 0) return;
                build(1, 1, n, a);
            }
            void updateSet(ll pos, ll val) { updateSet(1, 1, n, pos, val); }
            void updateDiv(ll pos, ll k) { updateDiv(1, 1, n, pos, k); }
            ll querySum(ll l, ll r) { return querySum(1, 1, n, l, r); }
        };
        vector<ll> a(n + 1);
        FOR(i, 1, n + 1) cin >> a[i];
        SegTree sg(n);
        sg.build(a);
        set<ll> st;
        FOR(i, 1, n + 1) if (a[i] != 0) st.insert(i);
        while (q--) {
            ll s, t, u;
            cin >> s >> t >> u;
            if (s == 1) {
                if (u != 0) st.insert(t);
                else st.erase(t);
                sg.updateSet(t, u);
            } else if (s == 2) {
                auto it = st.lower_bound(t);
                while (it != st.end() && *it <= u) {
                    ll pos = *it;
                    sg.updateDiv(pos, k);
                    if (sg.querySum(pos, pos) == 0) it = st.erase(it);
                    else ++it;
                }
            } else if (s == 3) {
                cout << sg.querySum(t, u) << '\n';
            }
        }
    };
    BlueCrowner;
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

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