oj.uz

Submission #501825

# Submission time Handle Problem Language Result Execution time Memory
501825 2022-01-04T16:10:07 Z blue Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 163 ms 9532 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 396 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3692 KB Output is correct
2 Correct 38 ms 4356 KB Output is correct
3 Correct 53 ms 7056 KB Output is correct
4 Correct 66 ms 8900 KB Output is correct
5 Correct 70 ms 9532 KB Output is correct
6 Correct 75 ms 9412 KB Output is correct
7 Correct 79 ms 9400 KB Output is correct
8 Correct 73 ms 9400 KB Output is correct
9 Correct 82 ms 9312 KB Output is correct
10 Correct 72 ms 9268 KB Output is correct
11 Correct 70 ms 9284 KB Output is correct
12 Correct 87 ms 9304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 572 KB Output is correct
2 Correct 13 ms 2108 KB Output is correct
3 Correct 16 ms 2160 KB Output is correct
4 Correct 33 ms 1360 KB Output is correct
5 Correct 49 ms 4356 KB Output is correct
6 Correct 53 ms 4432 KB Output is correct
7 Correct 48 ms 4396 KB Output is correct
8 Correct 54 ms 5688 KB Output is correct
9 Correct 52 ms 5664 KB Output is correct
10 Correct 46 ms 5680 KB Output is correct
11 Correct 48 ms 5612 KB Output is correct
12 Correct 50 ms 5652 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3616 KB Output is correct
2 Correct 71 ms 3708 KB Output is correct
3 Correct 79 ms 3200 KB Output is correct
4 Correct 66 ms 2500 KB Output is correct
5 Correct 108 ms 7068 KB Output is correct
6 Correct 124 ms 6836 KB Output is correct
7 Correct 105 ms 6864 KB Output is correct
8 Correct 131 ms 6936 KB Output is correct
9 Correct 139 ms 7124 KB Output is correct
10 Correct 145 ms 7024 KB Output is correct
11 Correct 105 ms 7112 KB Output is correct
12 Correct 163 ms 7000 KB Output is correct