oj.uz

Submission #776420

# Submission time Handle Problem Language Result Execution time Memory
776420 2023-07-07T20:52:47 Z ThegeekKnight16 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 381 ms 129976 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);
    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;
            cout << query(1, 1, N, L, R) << '\n';
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 128664 KB Output is correct
2 Correct 47 ms 128696 KB Output is correct
3 Correct 48 ms 128588 KB Output is correct
4 Incorrect 53 ms 128692 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 198 ms 129472 KB Output is correct
2 Correct 163 ms 129356 KB Output is correct
3 Correct 210 ms 129520 KB Output is correct
4 Correct 222 ms 129864 KB Output is correct
5 Correct 244 ms 129900 KB Output is correct
6 Correct 291 ms 129924 KB Output is correct
7 Correct 238 ms 129880 KB Output is correct
8 Correct 250 ms 129916 KB Output is correct
9 Correct 227 ms 129976 KB Output is correct
10 Correct 235 ms 129868 KB Output is correct
11 Correct 236 ms 129972 KB Output is correct
12 Correct 228 ms 129920 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 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 381 ms 129220 KB Output isn't correct
2 Halted 0 ms 0 KB -