oj.uz

Submission #559925

# Submission time Handle Problem Language Result Execution time Memory
559925 2022-05-11T01:05:34 Z maeola Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 62172 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()
    {
        if (K == 1)
            return;
        for (int i = 0; i < H - 1; i++)
            P[i] = P[i + 1];
        P[H - 1] = 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()
    {
        for (int k = 0; k < rolln; k++)
            pk.roll();
        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 336 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 13 ms 1172 KB Output is correct
5 Correct 21 ms 2124 KB Output is correct
6 Correct 22 ms 2164 KB Output is correct
7 Correct 22 ms 2160 KB Output is correct
8 Correct 21 ms 2132 KB Output is correct
9 Correct 21 ms 2132 KB Output is correct
10 Correct 23 ms 2172 KB Output is correct
11 Correct 21 ms 2132 KB Output is correct
12 Correct 23 ms 2172 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 31312 KB Output is correct
2 Correct 633 ms 22064 KB Output is correct
3 Correct 700 ms 48076 KB Output is correct
4 Correct 1097 ms 60984 KB Output is correct
5 Correct 1466 ms 61892 KB Output is correct
6 Correct 1500 ms 61976 KB Output is correct
7 Correct 1340 ms 61928 KB Output is correct
8 Correct 1428 ms 61900 KB Output is correct
9 Correct 2445 ms 62172 KB Output is correct
10 Correct 2473 ms 61844 KB Output is correct
11 Correct 2489 ms 61936 KB Output is correct
12 Correct 2441 ms 61912 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 4580 KB Output is correct
2 Correct 817 ms 27316 KB Output is correct
3 Correct 1512 ms 27488 KB Output is correct
4 Correct 4955 ms 16180 KB Output is correct
5 Execution timed out 5097 ms 60676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 32492 KB Time limit exceeded
2 Halted 0 ms 0 KB -