oj.uz

Submission #559941

# Submission time Handle Problem Language Result Execution time Memory
559941 2022-05-11T01:23:30 Z maeola Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 716 ms 62108 KB 
// trans rights

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int N, Q, K;
constexpr int H = 33;

struct Package
{
    ll P[H];
    void roll(int g)
    {
        if (K == 1)
            return;
        g = min(g, H);
        for (int i = 0; i < H - g; i++)
            P[i] = P[i + g];
        for (int i = H - g; i < H; i++)
            P[i] = 0;
    }
};

Package combine(const Package& a, const Package& b)
{
    Package c;
    for (int i = 0; i < H; i++)
        c.P[i] = a.P[i] + b.P[i];
    return c;
}

struct Node 
{
    int l, r;
    Node *lc, *rc;
    int rolln = 0;
    Package pk;
    Node(int l, int r) : l(l), r(r), lc(0), rc(0)
    {
        if (l != r)
        {
            int m = l + (r - l) / 2;
            lc = new Node(l, m);
            rc = new Node(m + 1, r);
        }
    }
    void clean()
    {
        pk.roll(rolln);
        if (l != r)
        {
            lc->rolln += rolln;
            rc->rolln += rolln;
        }
        rolln = 0;
    }
    void update(int p, int x)
    {
        clean();
        if (p < l or p > r)
            return;
        if (l == r)
        {
            pk.P[0] = x;
            for (int i = 1; i < H; i++)
                pk.P[i] = pk.P[i - 1] / K;
            return;
        }
        lc->update(p, x);
        rc->update(p, x);
        pk = combine(lc->pk, rc->pk);
    }
    void spray(int ql, int qr)
    {
        clean();
        if (qr < l or ql > r)
            return;
        if (ql <= l and qr >= r)
        {
            rolln++;
            clean();
            return;
        }
        lc->spray(ql, qr);
        rc->spray(ql, qr);
        pk = combine(lc->pk, rc->pk);
    }
    ll query(int ql, int qr)
    {
        clean();
        if (qr < l or ql > r)
            return 0;
        if (ql <= l and qr >= r)
            return pk.P[0];
        return lc->query(ql, qr) + rc->query(ql, qr);
    }
};

int main(int argc, const char *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> Q >> K;
    Node *root = new Node(1, N);
    for (int i = 1; i <= N; i++)
    {
        int a;
        cin >> a;
        root->update(i, a);
    }
    for (int k = 0; k < Q; k++)
    {
        int s, t, u;
        cin >> s >> t >> u;
        if (s == 1)
        {
            root->update(t, u);
        }else if (s == 2)
        {
            root->spray(t, u);
        }else if(s == 3)
        {
            cout << root->query(t, u) << '\n';
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 712 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 8 ms 1104 KB Output is correct
5 Correct 11 ms 2164 KB Output is correct
6 Correct 12 ms 2132 KB Output is correct
7 Correct 13 ms 2132 KB Output is correct
8 Correct 11 ms 2168 KB Output is correct
9 Correct 12 ms 2132 KB Output is correct
10 Correct 11 ms 2124 KB Output is correct
11 Correct 12 ms 2132 KB Output is correct
12 Correct 12 ms 2132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 29628 KB Output is correct
2 Correct 238 ms 20532 KB Output is correct
3 Correct 293 ms 46488 KB Output is correct
4 Correct 383 ms 59396 KB Output is correct
5 Correct 404 ms 60236 KB Output is correct
6 Correct 426 ms 60248 KB Output is correct
7 Correct 451 ms 60268 KB Output is correct
8 Correct 430 ms 60280 KB Output is correct
9 Correct 331 ms 60236 KB Output is correct
10 Correct 356 ms 60240 KB Output is correct
11 Correct 330 ms 60236 KB Output is correct
12 Correct 375 ms 60304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 4300 KB Output is correct
2 Correct 135 ms 27080 KB Output is correct
3 Correct 176 ms 27084 KB Output is correct
4 Correct 343 ms 15156 KB Output is correct
5 Correct 641 ms 60732 KB Output is correct
6 Correct 571 ms 61204 KB Output is correct
7 Correct 422 ms 61388 KB Output is correct
8 Correct 630 ms 61332 KB Output is correct
9 Correct 508 ms 61064 KB Output is correct
10 Correct 525 ms 61132 KB Output is correct
11 Correct 499 ms 61124 KB Output is correct
12 Correct 549 ms 61136 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 31212 KB Output is correct
2 Correct 398 ms 33136 KB Output is correct
3 Correct 302 ms 28236 KB Output is correct
4 Correct 357 ms 21268 KB Output is correct
5 Correct 716 ms 62040 KB Output is correct
6 Correct 623 ms 62108 KB Output is correct
7 Correct 623 ms 61928 KB Output is correct
8 Correct 616 ms 61952 KB Output is correct
9 Correct 528 ms 62008 KB Output is correct
10 Correct 532 ms 62056 KB Output is correct
11 Correct 522 ms 61996 KB Output is correct
12 Correct 519 ms 62020 KB Output is correct