oj.uz

Submission #776427

# Submission time Handle Problem Language Result Execution time Memory
776427 2023-07-07T21:16:35 Z ThegeekKnight16 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 670 ms 161480 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MAXX = 50;
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) const
    {
        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;
    // cerr << "REFRESHED" << '\n';
    int x = seg[pos].lz;
    if (x > MAXX) x = MAXX;
    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;
    for (int q = 0; q < Q; 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';
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int32_t main()':
sterilizing.cpp:111:10: warning: unused variable 'b' [-Wunused-variable]
  111 |     bool b = false;
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 159948 KB Output is correct
2 Correct 57 ms 159912 KB Output is correct
3 Correct 58 ms 159972 KB Output is correct
4 Correct 64 ms 159964 KB Output is correct
5 Correct 66 ms 160120 KB Output is correct
6 Correct 73 ms 160224 KB Output is correct
7 Correct 66 ms 160040 KB Output is correct
8 Correct 66 ms 160104 KB Output is correct
9 Correct 68 ms 160092 KB Output is correct
10 Correct 66 ms 160056 KB Output is correct
11 Correct 66 ms 160080 KB Output is correct
12 Correct 70 ms 160300 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 160780 KB Output is correct
2 Correct 187 ms 160656 KB Output is correct
3 Correct 201 ms 160984 KB Output is correct
4 Correct 240 ms 161144 KB Output is correct
5 Correct 276 ms 161252 KB Output is correct
6 Correct 277 ms 161288 KB Output is correct
7 Correct 272 ms 161176 KB Output is correct
8 Correct 281 ms 161312 KB Output is correct
9 Correct 259 ms 161276 KB Output is correct
10 Correct 260 ms 161228 KB Output is correct
11 Correct 265 ms 161340 KB Output is correct
12 Correct 296 ms 161308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 160100 KB Output is correct
2 Correct 142 ms 160460 KB Output is correct
3 Correct 185 ms 160412 KB Output is correct
4 Correct 436 ms 160512 KB Output is correct
5 Correct 641 ms 161072 KB Output is correct
6 Correct 643 ms 161020 KB Output is correct
7 Correct 246 ms 161252 KB Output is correct
8 Correct 645 ms 161096 KB Output is correct
9 Correct 485 ms 161112 KB Output is correct
10 Correct 482 ms 161104 KB Output is correct
11 Correct 475 ms 161116 KB Output is correct
12 Correct 482 ms 161044 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 160584 KB Output is correct
2 Correct 466 ms 160980 KB Output is correct
3 Correct 302 ms 160736 KB Output is correct
4 Correct 455 ms 160812 KB Output is correct
5 Correct 669 ms 161324 KB Output is correct
6 Correct 657 ms 161316 KB Output is correct
7 Correct 667 ms 161228 KB Output is correct
8 Correct 670 ms 161444 KB Output is correct
9 Correct 495 ms 161480 KB Output is correct
10 Correct 491 ms 161364 KB Output is correct
11 Correct 491 ms 161460 KB Output is correct
12 Correct 496 ms 161344 KB Output is correct