oj.uz

Submission #521768

# Submission time Handle Problem Language Result Execution time Memory
521768 2022-02-03T02:47:54 Z tengiz05 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 221 ms 9412 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100005;
int n, k;
struct Info {
    int mx;
    i64 sum;
    Info(int x = 0) : mx(x), sum(x) {}
};
Info operator+(const Info &a, const Info &b) {
    Info res;
    res.mx = std::max(a.mx, b.mx);
    res.sum = a.sum + b.sum;
    return res;
}
Info t[4 * N];
void modify(int p, int l, int r, int x, int y) {
    if (l == r - 1) {
        t[p] = Info(y);
        return;
    }
    int m = (l + r) / 2;
    if (x < m) {
        modify(2 * p, l, m, x, y);
    } else {
        modify(2 * p + 1, m, r, x, y);
    }
    t[p] = t[2 * p] + t[2 * p + 1];
}
void apply(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l || t[p].mx == 0) {
        return;
    }
    if (l == r - 1) {
        t[p] = Info(t[p].mx / k);
        return;
    }
    int m = (l + r) / 2;
    apply(2 * p, l, m, x, y);
    apply(2 * p + 1, m, r, x, y);
    t[p] = t[2 * p] + t[2 * p + 1];
}
Info query(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l) {
        return Info();
    }
    if (x <= l && r <= y) {
        return t[p];
    }
    int m = (l + r) / 2;
    return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int q;
    std::cin >> n >> q >> k;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        modify(1, 0, n, i, a[i]);
    }
    
    while (q--) {
        int op, x, y;
        std::cin >> op >> x >> y;
        
        x--;
        
        if (op == 1) {
            modify(1, 0, n, x, y);
        } else if (op == 2) {
            if (k > 1) {
                apply(1, 0, n, x, y);
            }
        } else {
            std::cout << query(1, 0, n, x, y).sum << "\n";
        }
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 3 ms 6476 KB Output is correct
3 Correct 4 ms 6476 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 6 ms 6604 KB Output is correct
6 Correct 6 ms 6604 KB Output is correct
7 Correct 6 ms 6588 KB Output is correct
8 Correct 6 ms 6604 KB Output is correct
9 Correct 6 ms 6604 KB Output is correct
10 Correct 5 ms 6584 KB Output is correct
11 Correct 6 ms 6592 KB Output is correct
12 Correct 6 ms 6604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7160 KB Output is correct
2 Correct 44 ms 7004 KB Output is correct
3 Correct 45 ms 7104 KB Output is correct
4 Correct 57 ms 7368 KB Output is correct
5 Correct 68 ms 9220 KB Output is correct
6 Correct 69 ms 9292 KB Output is correct
7 Correct 71 ms 9412 KB Output is correct
8 Correct 65 ms 9220 KB Output is correct
9 Correct 65 ms 9084 KB Output is correct
10 Correct 78 ms 9172 KB Output is correct
11 Correct 64 ms 9196 KB Output is correct
12 Correct 67 ms 9172 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6628 KB Output is correct
2 Correct 18 ms 6768 KB Output is correct
3 Correct 21 ms 6732 KB Output is correct
4 Correct 47 ms 6696 KB Output is correct
5 Correct 73 ms 7108 KB Output is correct
6 Correct 62 ms 6992 KB Output is correct
7 Correct 57 ms 7484 KB Output is correct
8 Correct 66 ms 8388 KB Output is correct
9 Correct 63 ms 8280 KB Output is correct
10 Correct 64 ms 8260 KB Output is correct
11 Correct 58 ms 8260 KB Output is correct
12 Correct 64 ms 8240 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6916 KB Output is correct
2 Correct 86 ms 6936 KB Output is correct
3 Correct 95 ms 6824 KB Output is correct
4 Correct 107 ms 6944 KB Output is correct
5 Correct 122 ms 7172 KB Output is correct
6 Correct 139 ms 7216 KB Output is correct
7 Correct 118 ms 7212 KB Output is correct
8 Correct 164 ms 7240 KB Output is correct
9 Correct 149 ms 7216 KB Output is correct
10 Correct 171 ms 7228 KB Output is correct
11 Correct 138 ms 7372 KB Output is correct
12 Correct 221 ms 7236 KB Output is correct