oj.uz

Submission #637096

# Submission time Handle Problem Language Result Execution time Memory
637096 2022-08-31T13:31:19 Z tvladm2009 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 3492 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) {
            spray(1, 1, n, l, r);
        } else {
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 420 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4227 ms 2184 KB Output is correct
2 Correct 2647 ms 1948 KB Output is correct
3 Correct 4435 ms 3268 KB Output is correct
4 Execution timed out 5084 ms 3308 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 9 ms 1620 KB Output is correct
3 Correct 13 ms 1620 KB Output is correct
4 Correct 47 ms 1052 KB Output is correct
5 Correct 57 ms 3168 KB Output is correct
6 Correct 46 ms 3208 KB Output is correct
7 Execution timed out 5064 ms 3360 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1864 KB Output is correct
2 Correct 74 ms 1980 KB Output is correct
3 Correct 84 ms 1876 KB Output is correct
4 Correct 92 ms 1340 KB Output is correct
5 Correct 102 ms 3320 KB Output is correct
6 Correct 117 ms 3344 KB Output is correct
7 Correct 100 ms 3492 KB Output is correct
8 Correct 145 ms 3432 KB Output is correct
9 Correct 128 ms 3400 KB Output is correct
10 Correct 146 ms 3412 KB Output is correct
11 Correct 107 ms 3444 KB Output is correct
12 Correct 217 ms 3452 KB Output is correct