oj.uz

Submission #933010

# Submission time Handle Problem Language Result Execution time Memory
933010 2024-02-24T19:39:33 Z borisAngelov Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 328 ms 77620 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);
}

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];
    }

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 40304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6712 KB Output is correct
2 Correct 44 ms 40072 KB Output is correct
3 Correct 69 ms 40188 KB Output is correct
4 Correct 182 ms 22508 KB Output is correct
5 Correct 284 ms 76268 KB Output is correct
6 Correct 277 ms 76372 KB Output is correct
7 Incorrect 280 ms 76148 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 173 ms 39768 KB Output is correct
2 Correct 189 ms 42068 KB Output is correct
3 Correct 138 ms 41068 KB Output is correct
4 Correct 194 ms 23092 KB Output is correct
5 Correct 328 ms 77588 KB Output is correct
6 Correct 278 ms 77608 KB Output is correct
7 Correct 301 ms 77588 KB Output is correct
8 Correct 284 ms 77564 KB Output is correct
9 Correct 208 ms 77536 KB Output is correct
10 Correct 220 ms 77620 KB Output is correct
11 Correct 215 ms 77392 KB Output is correct
12 Correct 216 ms 77420 KB Output is correct