oj.uz

Submission #776424

# Submission time Handle Problem Language Result Execution time Memory
776424 2023-07-07T21:05:18 Z ThegeekKnight16 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 547 ms 224244 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MAXX = 70;
int N, Q, K;
struct node
{
    array<int, MAXX> sum;
    int lz;

    node(array<int, MAXX> S = { 0 }, int LZ = 0) : sum(S), lz(LZ) {}

    node operator+(node outro)
    {
        node resp;
        for (int i = 0; i < MAXX; i++) resp.sum[i] = sum[i] + outro.sum[i];
        return resp;
    }
};
array<node, 4*MAXN> seg;
array<int, MAXN> v;

void refresh(int pos, int ini, int fim)
{
    if (seg[pos].lz == 0) return;
    int x = seg[pos].lz; seg[pos].lz = 0;

    for (int i = 0; i + x < MAXX; i++) seg[pos].sum[i] = seg[pos].sum[i+x];
    for (int i = MAXX - x; i < MAXX; i++) seg[pos].sum[i] = 0;

    if (ini == fim) return;

    int e = 2*pos; int d = 2*pos + 1;
    seg[e].lz += x;
    seg[d].lz += x;
}

void updatePlaca(int pos, int ini, int fim, int id, int val)
{
    refresh(pos, ini, fim);
    if (id < ini || id > fim) return;
    if (ini == fim)
    {
        seg[pos].sum[0] = val;
        for (int x = 1; x < MAXX; x++) seg[pos].sum[x] = (seg[pos].sum[x-1]/K);
        seg[pos].lz = 0;
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    updatePlaca(e, ini, m, id, val);
    updatePlaca(d, m+1, fim, id, val);
    seg[pos] = seg[e] + seg[d];
}

void updateSpray(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (K == 1) return;
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        seg[pos].lz++;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    updateSpray(e, ini, m, p, q);
    updateSpray(d, m+1, fim, p, q);
    seg[pos] = seg[e] + seg[d];
}

int query(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return seg[pos].sum[0];
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

void build(int pos, int ini, int fim)
{
    if (ini == fim)
    {
        seg[pos].sum[0] = v[ini];
        for (int x = 1; x < MAXX; x++) seg[pos].sum[x] = (seg[pos].sum[x-1]/K);
        seg[pos].lz = 0;
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos; int d = 2*pos + 1;
    build(e, ini, m);
    build(d, m+1, fim);
    seg[pos] = seg[e] + seg[d];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> Q >> K;
    for (int i = 1; i <= N; i++) cin >> v[i];
    build(1, 1, N);
    bool b = false;
    while (Q--)
    {
        int type;
        cin >> type;
        //Update Placa
        if (type == 1)
        {
            int id, val;
            cin >> id >> val;
            updatePlaca(1, 1, N, id, val);
        }
        //Update Spray
        else if (type == 2)
        {
            int L, R;
            cin >> L >> R;
            updateSpray(1, 1, N, L, R);
        }
        //Queries
        else
        {
            int L, R;
            cin >> L >> R;
            if (b) cout << '\n';
            b = true;
            cout << query(1, 1, N, L, R);
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 222548 KB Output is correct
2 Correct 76 ms 222572 KB Output is correct
3 Correct 112 ms 222664 KB Output is correct
4 Incorrect 94 ms 222616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 223716 KB Output is correct
2 Correct 278 ms 223676 KB Output is correct
3 Correct 283 ms 223816 KB Output is correct
4 Correct 328 ms 224068 KB Output is correct
5 Correct 371 ms 224076 KB Output is correct
6 Correct 363 ms 224140 KB Output is correct
7 Correct 364 ms 224164 KB Output is correct
8 Correct 376 ms 224104 KB Output is correct
9 Correct 349 ms 224168 KB Output is correct
10 Correct 362 ms 224244 KB Output is correct
11 Correct 360 ms 224128 KB Output is correct
12 Correct 368 ms 224204 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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