oj.uz

Submission #559608

# Submission time Handle Problem Language Result Execution time Memory
559608 2022-05-10T09:23:48 Z maeola Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 72216 KB 
// trans rights

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

using ll = long long;

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

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 (l == r)
        {
            pk.P[0] = x;
            for (int i = 1; i < H; i++)
                pk.P[i] = pk.P[i - 1] / K;
            return;
        }
        if (p <= lc->r)
        {
            lc->update(p, x);
            rc->clean();
        }
        else{
            rc->update(p, x);
            lc->clean();
        }
        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 4 ms 852 KB Output is correct
3 Correct 4 ms 1468 KB Output is correct
4 Correct 21 ms 1236 KB Output is correct
5 Correct 30 ms 2376 KB Output is correct
6 Correct 36 ms 2388 KB Output is correct
7 Correct 29 ms 2388 KB Output is correct
8 Correct 28 ms 2388 KB Output is correct
9 Correct 32 ms 2456 KB Output is correct
10 Correct 30 ms 2388 KB Output is correct
11 Correct 29 ms 2440 KB Output is correct
12 Correct 33 ms 2448 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 36168 KB Output is correct
2 Correct 638 ms 25472 KB Output is correct
3 Correct 778 ms 55464 KB Output is correct
4 Correct 1174 ms 70672 KB Output is correct
5 Correct 1541 ms 72216 KB Output is correct
6 Correct 1523 ms 72048 KB Output is correct
7 Correct 1610 ms 72204 KB Output is correct
8 Correct 1710 ms 72124 KB Output is correct
9 Correct 3057 ms 71976 KB Output is correct
10 Correct 2732 ms 72124 KB Output is correct
11 Correct 2542 ms 72192 KB Output is correct
12 Correct 2620 ms 72140 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 5180 KB Output is correct
2 Correct 1139 ms 31624 KB Output is correct
3 Correct 2221 ms 31824 KB Output is correct
4 Execution timed out 5062 ms 18500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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