oj.uz

Submission #668940

# Submission time Handle Problem Language Result Execution time Memory
668940 2022-12-05T08:40:12 Z stevancv Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 216 ms 3056 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 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 2192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 13 ms 1364 KB Output is correct
3 Correct 19 ms 1368 KB Output is correct
4 Correct 40 ms 864 KB Output is correct
5 Correct 59 ms 2416 KB Output is correct
6 Correct 55 ms 2372 KB Output is correct
7 Incorrect 62 ms 3056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1548 KB Output is correct
2 Correct 77 ms 1484 KB Output is correct
3 Correct 101 ms 1412 KB Output is correct
4 Correct 97 ms 1024 KB Output is correct
5 Correct 113 ms 2640 KB Output is correct
6 Correct 131 ms 2648 KB Output is correct
7 Correct 108 ms 2644 KB Output is correct
8 Correct 154 ms 2652 KB Output is correct
9 Correct 140 ms 2572 KB Output is correct
10 Correct 162 ms 2724 KB Output is correct
11 Correct 120 ms 2564 KB Output is correct
12 Correct 216 ms 2616 KB Output is correct