oj.uz

Submission #559938

# Submission time Handle Problem Language Result Execution time Memory
559938 2022-05-11T01:21:58 Z maeola Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 430 ms 62352 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;
        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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 30060 KB Output is correct
2 Correct 225 ms 20612 KB Output is correct
3 Correct 271 ms 46628 KB Output is correct
4 Correct 364 ms 59796 KB Output is correct
5 Correct 415 ms 60628 KB Output is correct
6 Correct 415 ms 60816 KB Output is correct
7 Correct 430 ms 60700 KB Output is correct
8 Correct 415 ms 60552 KB Output is correct
9 Correct 338 ms 60712 KB Output is correct
10 Correct 332 ms 60620 KB Output is correct
11 Correct 343 ms 60824 KB Output is correct
12 Correct 337 ms 60568 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 8148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 62352 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -