Submission #501825

#	Time	Username	Problem	Language	Result	Execution time	Memory
501825		blue	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	163 ms	9532 KiB

sterilizing

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

int N, Q, K;
vll C;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> Q >> K;
    C = vll(1+N);
    for(int i = 1; i <= N; i++) cin >> C[i];

    vll BIT(1+N, 0);
    for(int i = 1; i <= N; i++)
        for(int j = i; j <= N; j += j&-j)
            BIT[j] += C[i];

    set<int> pos;
    for(int i = 1; i <= N; i++)
        if(C[i] > 0)
            pos.insert(i);

    for(int j = 1; j <= Q; j++)
    {
        int S;
        cin >> S;

        if(S == 1)
        {
            ll a, b;
            cin >> a >> b;

            ll adj = b - C[a];

            if(b == 0) pos.erase(a);
            else pos.insert(a);

            for(int j = a; j <= N; j += j&-j)
                BIT[j] += adj;

            C[a] = b;
        }
        else if(S == 2)
        {

            int l, r;
            cin >> l >> r;


                if(K == 1) continue;

            vi erase_pos;

            auto it = pos.lower_bound(l);
            while(it != pos.end())
            {
                int i = *it;

                if(i > r) break;

                if(C[i] / K == 0) erase_pos.push_back(i);

                ll adj = (C[i] / K) - C[i];

                for(int j = i; j <= N; j += j&-j)
                    BIT[j] += adj;

                C[i] /= K;

                it++;
            }

            for(int e: erase_pos) pos.erase(e);
        }
        else
        {
            int l, r;
            cin >> l >> r;

            ll ans = 0;

            for(int i = r; i >= 1; i -= i&-i)
                ans += BIT[i];
            for(int i = l-1; i >= 1; i -= i&-i)
                ans -= BIT[i];

            cout << ans << '\n';
        }
    }
}

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