oj.uz

Submission #933012

# Submission time Handle Problem Language Result Execution time Memory
933012 2024-02-24T19:43:50 Z borisAngelov Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 311 ms 78156 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int maxStates = 30;

int n, q, k;

int a[maxn];

long long tree[4 * maxn][maxStates + 5];
int lazy[4 * maxn];

void build(int node, int l, int r)
{
    lazy[node] = 0;

    if (l == r)
    {
        tree[node][0] = a[l];

        for (int i = 1; i <= maxStates; ++i)
        {
            tree[node][i] = tree[node][i - 1] / k;
        }

        return;
    }

    int mid = (l + r) / 2;

    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);

    for (int i = 0; i <= maxStates; ++i)
    {
        tree[node][i] = tree[2 * node][i] + tree[2 * node + 1][i];
    }
}

void pushLazy(int node, int l, int r)
{
    if (lazy[node] == 0)
    {
        return;
    }

    for (int i = 0; i <= maxStates; ++i)
    {
        if (i + lazy[node] <= maxStates)
        {
            tree[node][i] = tree[node][i + lazy[node]];
        }
        else
        {
            tree[node][i] = 0;
        }
    }

    if (l != r)
    {
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }

    lazy[node] = 0;
}

void updatePoint(int node, int l, int r, int pos, int val)
{
    pushLazy(node, l, r);

    if (l == r)
    {
        lazy[node] = 0;

        a[pos] = val;
        tree[node][0] = a[pos];

        for (int i = 1; i <= maxStates; ++i)
        {
            tree[node][i] = tree[node][i - 1] / k;
        }

        return;
    }

    int mid = (l + r) / 2;

    if (pos <= mid)
    {
        updatePoint(2 * node, l, mid, pos, val);
    }
    else
    {
        updatePoint(2 * node + 1, mid + 1, r, pos, val);
    }

    pushLazy(2 * node, l, mid);
    pushLazy(2 * node + 1, mid + 1, r);

    for (int i = 0; i <= maxStates; ++i)
    {
        tree[node][i] = tree[2 * node][i] + tree[2 * node + 1][i];
    }
}

void updateRange(int node, int l, int r, int ql, int qr)
{
    pushLazy(node, l, r);

    if (l > qr || r < ql)
    {
        return;
    }

    if (ql <= l && r <= qr)
    {
        ++lazy[node];
        pushLazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    updateRange(2 * node, l, mid, ql, qr);
    updateRange(2 * node + 1, mid + 1, r, ql, qr);

    for (int i = 0; i <= maxStates; ++i)
    {
        tree[node][i] = tree[2 * node][i] + tree[2 * node + 1][i];
    }
}

long long query(int node, int l, int r, int ql, int qr)
{
    pushLazy(node, l, r);

    if (l > qr || r < ql)
    {
        return 0;
    }

    if (ql <= l && r <= qr)
    {
        return tree[node][0];
    }

    int mid = (l + r) / 2;

    return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
}

struct FenwickTree
{
    long long fen[maxn];

    void update(int pos, int val)
    {
        for (int i = pos; i <= n; i += (i & (-i)))
        {
            fen[i] += val;
        }
    }

    long long query(int pos)
    {
        long long ans = 0;

        for (int i = pos; i >= 1; i -= (i & (-i)))
        {
            ans += fen[i];
        }

        return ans;
    }
};

FenwickTree bit;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q >> k;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    if (k == 1)
    {
        for (int i = 1; i <= n; ++i)
        {
            bit.update(i, a[i]);
        }

        for (int i = 1; i <= q; ++i)
        {
            int type;
            cin >> type;

            if (type == 1)
            {
                int pos, val;
                cin >> pos >> val;
                bit.update(pos, val - a[pos]);
                a[pos] = val;
            }
            else if (type == 2)
            {
                int l, r;
                cin >> l >> r;
            }
            else if (type == 3)
            {
                int l, r;
                cin >> l >> r;
                cout << bit.query(r) - bit.query(l - 1) << "\n";
            }
        }

        return 0;
    }

    build(1, 1, n);

    for (int i = 1; i <= q; ++i)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            updatePoint(1, 1, n, pos, val);
        }
        else if (type == 2)
        {
            int l, r;
            cin >> l >> r;
            updateRange(1, 1, n, l, r);
        }
        else if (type == 3)
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 6 ms 6704 KB Output is correct
8 Correct 5 ms 6492 KB Output is correct
9 Correct 5 ms 6492 KB Output is correct
10 Correct 6 ms 6708 KB Output is correct
11 Correct 5 ms 6492 KB Output is correct
12 Correct 6 ms 6704 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3164 KB Output is correct
2 Correct 22 ms 4832 KB Output is correct
3 Correct 19 ms 4700 KB Output is correct
4 Correct 24 ms 5456 KB Output is correct
5 Correct 32 ms 5884 KB Output is correct
6 Correct 29 ms 5968 KB Output is correct
7 Correct 29 ms 5980 KB Output is correct
8 Correct 30 ms 6004 KB Output is correct
9 Correct 28 ms 5648 KB Output is correct
10 Correct 28 ms 5716 KB Output is correct
11 Correct 28 ms 5724 KB Output is correct
12 Correct 28 ms 5716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8956 KB Output is correct
2 Correct 46 ms 39608 KB Output is correct
3 Correct 68 ms 39512 KB Output is correct
4 Correct 212 ms 21084 KB Output is correct
5 Correct 311 ms 76644 KB Output is correct
6 Correct 281 ms 76764 KB Output is correct
7 Correct 24 ms 3164 KB Output is correct
8 Correct 277 ms 78156 KB Output is correct
9 Correct 195 ms 77908 KB Output is correct
10 Correct 247 ms 78088 KB Output is correct
11 Correct 196 ms 77940 KB Output is correct
12 Correct 195 ms 78032 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 40032 KB Output is correct
2 Correct 192 ms 39908 KB Output is correct
3 Correct 118 ms 39644 KB Output is correct
4 Correct 187 ms 21132 KB Output is correct
5 Correct 285 ms 76880 KB Output is correct
6 Correct 295 ms 77004 KB Output is correct
7 Correct 307 ms 77008 KB Output is correct
8 Correct 281 ms 76884 KB Output is correct
9 Correct 206 ms 76964 KB Output is correct
10 Correct 205 ms 76884 KB Output is correct
11 Correct 201 ms 77012 KB Output is correct
12 Correct 216 ms 77044 KB Output is correct