oj.uz

Submission #668938

# Submission time Handle Problem Language Result Execution time Memory
668938 2022-12-05T08:39:04 Z stevancv Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 5068 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) 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4577 ms 3792 KB Output is correct
2 Correct 2792 ms 3540 KB Output is correct
3 Correct 4675 ms 4320 KB Output is correct
4 Execution timed out 5086 ms 4532 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 852 KB Output is correct
2 Correct 13 ms 1744 KB Output is correct
3 Correct 18 ms 1740 KB Output is correct
4 Correct 42 ms 1996 KB Output is correct
5 Correct 57 ms 3896 KB Output is correct
6 Correct 58 ms 3800 KB Output is correct
7 Execution timed out 5033 ms 3460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3200 KB Output is correct
2 Correct 80 ms 3236 KB Output is correct
3 Correct 97 ms 2624 KB Output is correct
4 Correct 107 ms 2780 KB Output is correct
5 Correct 131 ms 4972 KB Output is correct
6 Correct 131 ms 4996 KB Output is correct
7 Correct 115 ms 5068 KB Output is correct
8 Correct 166 ms 5060 KB Output is correct
9 Correct 164 ms 4904 KB Output is correct
10 Correct 169 ms 5020 KB Output is correct
11 Correct 134 ms 4892 KB Output is correct
12 Correct 212 ms 4936 KB Output is correct