oj.uz

Submission #637177

# Submission time Handle Problem Language Result Execution time Memory
637177 2022-08-31T17:48:01 Z tvladm2009 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 200 ms 6072 KB 
#include <iostream>
#define int long long

using namespace std;

const int MAX_N = 1e5;
int a[MAX_N + 1];
int aint[4 * MAX_N + 1];
int n, q, k;

void build(int v, int l, int r) {
    if (l == r) {
        aint[v] = a[l];
    } else {
        int mid = (l + r) / 2;
        build(2 * v, l, mid);
        build(2 * v + 1, mid + 1, r);
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

void update(int v, int l, int r, int pos, int val) {
    if (l == r) {
        aint[v] = val;
    } else {
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2 * v, l, mid, pos, val);
        } else {
            update(2 * v + 1, mid + 1, r, pos, val);
        }
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

void spray(int v, int l, int r, int p, int q) {
    if (p > q || !aint[v]) {
        return;
    }
    if (l == r) {
        aint[v] /= k;
    } else {
        int mid = (l + r) / 2;
        spray(2 * v, l, mid, p, min(mid, q));
        spray(2 * v + 1, mid + 1, r, max(p, mid + 1), q);
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

int query(int v, int l, int r, int p, int q) {
    if (p > q) {
        return 0;
    } else if (l == p && r == q) {
        return aint[v];
    } else {
        int mid = (l + r) / 2;
        return query(2 * v, l, mid, p, min(mid, q)) + query(2 * v + 1, mid + 1, r, max(p, mid + 1), q);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int j = 1; j <= q; j++) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            update(1, 1, n, l, r);
        } else if (t == 2 && k > 1) {
            spray(1, 1, n, l, r);
        } else if (t == 3) {
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2156 KB Output is correct
2 Correct 38 ms 2060 KB Output is correct
3 Correct 31 ms 3404 KB Output is correct
4 Correct 45 ms 3916 KB Output is correct
5 Correct 47 ms 6064 KB Output is correct
6 Correct 48 ms 6012 KB Output is correct
7 Correct 47 ms 6032 KB Output is correct
8 Correct 49 ms 6072 KB Output is correct
9 Correct 50 ms 5840 KB Output is correct
10 Correct 49 ms 5912 KB Output is correct
11 Correct 47 ms 5832 KB Output is correct
12 Correct 47 ms 5904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 528 KB Output is correct
2 Correct 9 ms 1620 KB Output is correct
3 Correct 12 ms 1728 KB Output is correct
4 Correct 36 ms 1072 KB Output is correct
5 Correct 53 ms 3204 KB Output is correct
6 Correct 51 ms 3204 KB Output is correct
7 Correct 41 ms 3332 KB Output is correct
8 Correct 46 ms 4556 KB Output is correct
9 Correct 43 ms 4432 KB Output is correct
10 Correct 43 ms 4464 KB Output is correct
11 Correct 45 ms 4488 KB Output is correct
12 Correct 48 ms 4436 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1940 KB Output is correct
2 Correct 75 ms 2092 KB Output is correct
3 Correct 86 ms 1856 KB Output is correct
4 Correct 93 ms 1488 KB Output is correct
5 Correct 107 ms 3500 KB Output is correct
6 Correct 124 ms 3536 KB Output is correct
7 Correct 98 ms 3488 KB Output is correct
8 Correct 143 ms 3628 KB Output is correct
9 Correct 134 ms 3696 KB Output is correct
10 Correct 156 ms 3604 KB Output is correct
11 Correct 112 ms 3608 KB Output is correct
12 Correct 200 ms 3536 KB Output is correct