oj.uz

Submission #501823

# Submission time Handle Problem Language Result Execution time Memory
501823 2022-01-04T16:08:08 Z blue Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9416 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;

            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 3 ms 328 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 452 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 3596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 580 KB Output is correct
2 Correct 13 ms 2124 KB Output is correct
3 Correct 17 ms 2228 KB Output is correct
4 Correct 34 ms 1336 KB Output is correct
5 Correct 51 ms 4616 KB Output is correct
6 Correct 56 ms 4692 KB Output is correct
7 Execution timed out 5081 ms 4556 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3764 KB Output is correct
2 Correct 62 ms 5444 KB Output is correct
3 Correct 88 ms 4440 KB Output is correct
4 Correct 73 ms 4416 KB Output is correct
5 Correct 105 ms 9416 KB Output is correct
6 Correct 121 ms 9260 KB Output is correct
7 Correct 110 ms 9284 KB Output is correct
8 Correct 144 ms 9400 KB Output is correct
9 Correct 118 ms 9284 KB Output is correct
10 Correct 129 ms 9324 KB Output is correct
11 Correct 107 ms 9252 KB Output is correct
12 Correct 162 ms 9240 KB Output is correct