oj.uz

Submission #361755

# Submission time Handle Problem Language Result Execution time Memory
361755 2021-01-31T14:19:24 Z RyoPham Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1567 ms 8940 KB 
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;

int n, Q, K;
int a[maxn];

struct segment_tree
{
    lli total[maxn * 4];
    pair<int, int> min_val[maxn * 4];

    void build(int x, int l, int r)
    {
        if(l == r)
        {
            total[x] = a[l];
            min_val[x] = make_pair(total[x] == 0 ? 1 : 0, l);
            return;
        }
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2 + 1, mid + 1, r);
        total[x] = total[x * 2] + total[x * 2 + 1];
        min_val[x] = min(min_val[x * 2], min_val[x * 2 + 1]);
    }

    pair<int, int> get(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R || L > R) return make_pair(1, n + 1);
        if(l >= L && r <= R)
            return min_val[x];
        int mid = (l + r) / 2;
        return min(get(x * 2, l, mid, L, R),
                   get(x * 2 + 1, mid + 1, r, L, R));
    }

    void spray(int x, int l, int r, int p)
    {
        if(l == r)
        {
            total[x] /= K;
            min_val[x] = make_pair(total[x] == 0 ? 1 : 0, l);
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) spray(x * 2, l, mid, p);
        else spray(x * 2 + 1, mid + 1, r, p);
        total[x] = total[x * 2] + total[x * 2 + 1];
        min_val[x] = min(min_val[x * 2], min_val[x * 2 + 1]);
    }

    void update(int x, int l, int r, int p, int k)
    {
        if(l == r)
        {
            total[x] = k;
            min_val[x] = make_pair(total[x] == 0 ? 1 : 0, l);
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) update(x * 2, l, mid, p, k);
        else update(x * 2 + 1, mid + 1, r, p, k);
        total[x] = total[x * 2] + total[x * 2 + 1];
        min_val[x] = min(min_val[x * 2], min_val[x * 2 + 1]);
    }

    lli get_total(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R) return 0;
        if(l >= L && r <= R)
            return total[x];
        int mid = (l + r) / 2;
        return get_total(x * 2, l, mid, L, R) + get_total(x * 2 + 1, mid + 1, r, L, R);
    }
} tree;

void read_input()
{
    cin >> n >> Q >> K;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
}

void solve()
{
    tree.build(1, 1, n);
    for(; Q > 0; --Q)
    {
        int type, x, y;
        cin >> type >> x >> y;
        if(type == 1)
            tree.update(1, 1, n, x, y);
        else if(type == 2)
        {
            if(K == 1) continue;
            auto t = tree.get(1, 1, n, x, y);
            while(t.fi == 0)
            {
                tree.spray(1, 1, n, t.se);
                t = tree.get(1, 1, n, t.se + 1, y);
            }
        }
        else cout << tree.get_total(1, 1, n, x, y) << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3564 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct
3 Correct 7 ms 3564 KB Output is correct
4 Correct 18 ms 3564 KB Output is correct
5 Correct 19 ms 3692 KB Output is correct
6 Correct 13 ms 3692 KB Output is correct
7 Correct 17 ms 3692 KB Output is correct
8 Correct 17 ms 3692 KB Output is correct
9 Correct 22 ms 3692 KB Output is correct
10 Correct 18 ms 3692 KB Output is correct
11 Correct 16 ms 3692 KB Output is correct
12 Correct 19 ms 3692 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7020 KB Output is correct
2 Correct 52 ms 6636 KB Output is correct
3 Correct 47 ms 7788 KB Output is correct
4 Correct 61 ms 8556 KB Output is correct
5 Correct 70 ms 8812 KB Output is correct
6 Correct 88 ms 8940 KB Output is correct
7 Correct 75 ms 8940 KB Output is correct
8 Correct 76 ms 8812 KB Output is correct
9 Correct 66 ms 8812 KB Output is correct
10 Correct 68 ms 8788 KB Output is correct
11 Correct 67 ms 8684 KB Output is correct
12 Correct 67 ms 8728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4204 KB Output is correct
2 Correct 26 ms 4972 KB Output is correct
3 Correct 34 ms 5228 KB Output is correct
4 Correct 74 ms 5332 KB Output is correct
5 Correct 112 ms 7404 KB Output is correct
6 Correct 110 ms 7404 KB Output is correct
7 Correct 67 ms 7532 KB Output is correct
8 Correct 117 ms 7404 KB Output is correct
9 Correct 98 ms 7276 KB Output is correct
10 Correct 98 ms 7276 KB Output is correct
11 Correct 105 ms 7404 KB Output is correct
12 Correct 102 ms 7276 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 6636 KB Output is correct
2 Correct 333 ms 6764 KB Output is correct
3 Correct 665 ms 6124 KB Output is correct
4 Correct 424 ms 6124 KB Output is correct
5 Correct 601 ms 8664 KB Output is correct
6 Correct 773 ms 8940 KB Output is correct
7 Correct 560 ms 8812 KB Output is correct
8 Correct 1046 ms 8812 KB Output is correct
9 Correct 854 ms 8556 KB Output is correct
10 Correct 1053 ms 8684 KB Output is correct
11 Correct 639 ms 8684 KB Output is correct
12 Correct 1567 ms 8536 KB Output is correct