oj.uz

Submission #601364

# Submission time Handle Problem Language Result Execution time Memory
601364 2022-07-21T18:39:23 Z elkernos Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 211 ms 7712 KB 
#include <bits/stdc++.h>

using namespace std;

struct T {
    long long sum = 0;
    int mark = 0;
    void init(int x)
    {
        sum = x;
        mark = (x == 0);
    }
    void merge(T a, T b)
    {
        sum = a.sum + b.sum;
        mark = a.mark & b.mark;
    }
};

T tr[1 << 18];
int a[1 << 18];
int k;
#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2

void init(int v, int l, int r)
{
    if(l == r) {
        tr[v].init(a[l]);
        return;
    }
    init(lc, l, m), init(rc, m + 1, r);
    tr[v].merge(tr[lc], tr[rc]);
}
void point(int v, int l, int r, int pos, int val)
{
    if(l == r) {
        tr[v].init(val);
        return;
    }
    if(pos <= m) {
        point(lc, l, m, pos, val);
    }
    else {
        point(rc, m + 1, r, pos, val);
    }
    tr[v].merge(tr[lc], tr[rc]);
}
void range(int v, int l, int r, int ql, int qr)
{
    if(r < ql || qr < l || tr[v].mark) {
        return;
    }
    if(l == r) {
        tr[v].init(tr[v].sum / k);
        return;
    }
    range(lc, l, m, ql, qr), range(rc, m + 1, r, ql, qr);
    tr[v].merge(tr[lc], tr[rc]);
}
long long sum(int v, int l, int r, int ql, int qr)
{
    if(r < ql || qr < l) {
        return 0;
    }
    if(ql <= l && r <= qr) {
        return tr[v].sum;
    }
    return sum(lc, l, m, ql, qr) + sum(rc, m + 1, r, ql, qr);
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    init(1, 1, n);
    for(int i = 1; i <= q; ++i) {
        int t;
        cin >> t;
        if(t == 1) {
            int a, b;
            cin >> a >> b;
            point(1, 1, n, a, b);
        }
        else if(t == 2) {
            int a, b;
            cin >> a >> b;
            if(k > 1) {
                range(1, 1, n, a, b);
            }
        }
        else if(t == 3) {
            int a, b;
            cin >> a >> b;
            cout << sum(1, 1, n, a, b) << '\n';
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 532 KB Output is correct
9 Correct 4 ms 480 KB Output is correct
10 Correct 3 ms 532 KB Output is correct
11 Correct 3 ms 472 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4908 KB Output is correct
2 Correct 38 ms 4444 KB Output is correct
3 Correct 34 ms 6604 KB Output is correct
4 Correct 42 ms 7248 KB Output is correct
5 Correct 56 ms 7712 KB Output is correct
6 Correct 72 ms 7688 KB Output is correct
7 Correct 74 ms 7628 KB Output is correct
8 Correct 57 ms 7676 KB Output is correct
9 Correct 50 ms 7512 KB Output is correct
10 Correct 49 ms 7564 KB Output is correct
11 Correct 51 ms 7544 KB Output is correct
12 Correct 48 ms 7568 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 980 KB Output is correct
2 Correct 12 ms 2772 KB Output is correct
3 Correct 21 ms 2936 KB Output is correct
4 Correct 40 ms 2600 KB Output is correct
5 Correct 51 ms 6292 KB Output is correct
6 Correct 54 ms 6372 KB Output is correct
7 Correct 46 ms 6348 KB Output is correct
8 Correct 55 ms 6236 KB Output is correct
9 Correct 49 ms 6132 KB Output is correct
10 Correct 46 ms 6092 KB Output is correct
11 Correct 45 ms 6096 KB Output is correct
12 Correct 63 ms 6084 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4240 KB Output is correct
2 Correct 84 ms 4480 KB Output is correct
3 Correct 116 ms 3824 KB Output is correct
4 Correct 99 ms 3376 KB Output is correct
5 Correct 135 ms 7500 KB Output is correct
6 Correct 134 ms 7480 KB Output is correct
7 Correct 108 ms 7456 KB Output is correct
8 Correct 160 ms 7504 KB Output is correct
9 Correct 200 ms 7428 KB Output is correct
10 Correct 170 ms 7372 KB Output is correct
11 Correct 122 ms 7372 KB Output is correct
12 Correct 211 ms 7348 KB Output is correct