oj.uz

Submission #637095

# Submission time Handle Problem Language Result Execution time Memory
637095 2022-08-31T13:29:54 Z tvladm2009 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 5884 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() {
    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 3 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 412 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 7 ms 392 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 7 ms 448 KB Output is correct
10 Correct 6 ms 476 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 8 ms 476 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4604 ms 2124 KB Output is correct
2 Correct 2790 ms 3624 KB Output is correct
3 Correct 4673 ms 4880 KB Output is correct
4 Execution timed out 5090 ms 5336 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 468 KB Output is correct
2 Correct 24 ms 1616 KB Output is correct
3 Correct 49 ms 1664 KB Output is correct
4 Correct 117 ms 1168 KB Output is correct
5 Correct 138 ms 3140 KB Output is correct
6 Correct 140 ms 3156 KB Output is correct
7 Execution timed out 5059 ms 3532 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 1984 KB Output is correct
2 Correct 152 ms 3624 KB Output is correct
3 Correct 134 ms 2960 KB Output is correct
4 Correct 185 ms 2968 KB Output is correct
5 Correct 218 ms 5836 KB Output is correct
6 Correct 253 ms 5820 KB Output is correct
7 Correct 209 ms 5760 KB Output is correct
8 Correct 261 ms 5884 KB Output is correct
9 Correct 246 ms 5676 KB Output is correct
10 Correct 268 ms 5752 KB Output is correct
11 Correct 243 ms 5636 KB Output is correct
12 Correct 308 ms 5756 KB Output is correct