oj.uz

Submission #501824

# Submission time Handle Problem Language Result Execution time Memory
501824 2022-01-04T16:09:52 Z blue Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 177 ms 7160 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)
        {
            if(K == 1) continue;
            int l, r;
            cin >> l >> r;

            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 6584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 576 KB Output is correct
2 Correct 13 ms 2104 KB Output is correct
3 Correct 17 ms 2156 KB Output is correct
4 Correct 35 ms 1344 KB Output is correct
5 Correct 57 ms 4300 KB Output is correct
6 Correct 68 ms 4304 KB Output is correct
7 Incorrect 46 ms 5168 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3652 KB Output is correct
2 Correct 76 ms 3772 KB Output is correct
3 Correct 79 ms 3256 KB Output is correct
4 Correct 71 ms 2512 KB Output is correct
5 Correct 112 ms 6848 KB Output is correct
6 Correct 131 ms 6864 KB Output is correct
7 Correct 108 ms 6796 KB Output is correct
8 Correct 158 ms 6948 KB Output is correct
9 Correct 131 ms 7160 KB Output is correct
10 Correct 137 ms 7000 KB Output is correct
11 Correct 108 ms 7120 KB Output is correct
12 Correct 177 ms 6988 KB Output is correct