Submission #776424

#	Time	Username	Problem	Language	Result	Execution time	Memory
776424		ThegeekKnight16	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	547 ms	224244 KiB

sterilizing

#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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75