oj.uz

Submission #668942

# Submission time Handle Problem Language Result Execution time Memory
668942 2022-12-05T08:43:27 Z stevancv Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 232 ms 5268 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const ll linf = 1e18;
ll st[4 * N];
void Update(int node, int l, int r, int x, int y) {
    if (l == r) {st[node] = y; return;}
    int mid = l + r >> 1;
    if (x <= mid) Update(2 * node, l, mid, x, y);
    else Update(2 * node + 1, mid + 1, r, x, y);
    st[node] = st[2 * node] + st[2 * node + 1];
}
void Spray(int node, int l, int r, int ql, int qr, int k) {
    if (r < ql || qr < l || st[node] == 0) return;
    if (l == r) {st[node] /= k; return;}
    int mid = l + r >> 1;
    Spray(2 * node, l, mid, ql, qr, k);
    Spray(2 * node + 1, mid + 1, r, ql, qr, k);
    st[node] = st[2 * node] + st[2 * node + 1];
}
ll Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return 0;
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Get(2 * node, l, mid, ql, qr) + Get(2 * node + 1, mid + 1, r, ql, qr);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, k;
    cin >> n >> q >> k;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        Update(1, 0, n - 1, i, x);
    }
    while (q--) {
        int ty, x, y;
        cin >> ty >> x >> y;
        if (ty == 1) Update(1, 0, n - 1, x - 1, y);
        else if (ty == 2 && k > 1) Spray(1, 0, n - 1, x - 1, y - 1, k);
        else if (ty == 3) cout << Get(1, 0, n - 1, x - 1, y - 1) << en;
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'void Update(int, int, int, int, int)':
sterilizing.cpp:14:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     int mid = l + r >> 1;
      |               ~~^~~
sterilizing.cpp: In function 'void Spray(int, int, int, int, int, int)':
sterilizing.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = l + r >> 1;
      |               ~~^~~
sterilizing.cpp: In function 'long long int Get(int, int, int, int, int)':
sterilizing.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~

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 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 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 5 ms 468 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 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1764 KB Output is correct
2 Correct 41 ms 1688 KB Output is correct
3 Correct 37 ms 2624 KB Output is correct
4 Correct 47 ms 2964 KB Output is correct
5 Correct 59 ms 5192 KB Output is correct
6 Correct 73 ms 5196 KB Output is correct
7 Correct 60 ms 5196 KB Output is correct
8 Correct 59 ms 5268 KB Output is correct
9 Correct 54 ms 5068 KB Output is correct
10 Correct 62 ms 5112 KB Output is correct
11 Correct 55 ms 5068 KB Output is correct
12 Correct 58 ms 5088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct
2 Correct 17 ms 1364 KB Output is correct
3 Correct 17 ms 1368 KB Output is correct
4 Correct 42 ms 864 KB Output is correct
5 Correct 60 ms 2388 KB Output is correct
6 Correct 58 ms 2400 KB Output is correct
7 Correct 50 ms 2444 KB Output is correct
8 Correct 58 ms 3856 KB Output is correct
9 Correct 57 ms 3660 KB Output is correct
10 Correct 53 ms 3692 KB Output is correct
11 Correct 58 ms 3664 KB Output is correct
12 Correct 52 ms 3652 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1504 KB Output is correct
2 Correct 80 ms 1452 KB Output is correct
3 Correct 87 ms 1484 KB Output is correct
4 Correct 105 ms 1124 KB Output is correct
5 Correct 117 ms 2592 KB Output is correct
6 Correct 131 ms 2608 KB Output is correct
7 Correct 108 ms 2540 KB Output is correct
8 Correct 165 ms 2744 KB Output is correct
9 Correct 142 ms 2692 KB Output is correct
10 Correct 161 ms 2672 KB Output is correct
11 Correct 126 ms 2640 KB Output is correct
12 Correct 232 ms 2724 KB Output is correct