oj.uz

Submission #776421

# Submission time Handle Problem Language Result Execution time Memory
776421 2023-07-07T21:01:53 Z ThegeekKnight16 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 344 ms 129980 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MAXX = 40;
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 51 ms 128700 KB Output is correct
2 Correct 47 ms 128700 KB Output is correct
3 Correct 47 ms 128672 KB Output is correct
4 Incorrect 52 ms 128700 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 196 ms 129476 KB Output is correct
2 Correct 162 ms 129272 KB Output is correct
3 Correct 189 ms 129564 KB Output is correct
4 Correct 211 ms 129980 KB Output is correct
5 Correct 248 ms 129868 KB Output is correct
6 Correct 242 ms 129908 KB Output is correct
7 Correct 258 ms 129940 KB Output is correct
8 Correct 252 ms 129868 KB Output is correct
9 Correct 234 ms 129964 KB Output is correct
10 Correct 232 ms 129948 KB Output is correct
11 Correct 251 ms 129972 KB Output is correct
12 Correct 233 ms 129896 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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