oj.uz

Submission #970758

# Submission time Handle Problem Language Result Execution time Memory
970758 2024-04-27T08:12:58 Z Beerus13 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 206 ms 7564 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;

struct node {
    ll sum, mx;
    node() {}
    node(ll sum, ll mx) : sum(sum), mx(mx) {}
};

node operator + (node &a, node &b) {
    node res;
    res.sum = a.sum + b.sum;
    res.mx = max(a.mx, b.mx);
    return res;
}

int n, q, k;
node st[N << 2];

void update_point(int u, int val) {
    int id = 1, l = 1, r = n;
    while(l < r) {
        int m = l + r >> 1;
        if(u > m) id = id << 1 | 1, l = m + 1;
        else id = id << 1, r = m;
    }
    st[id] = node(val, val);
    while(id > 1) id = id >> 1, st[id] = st[id << 1] + st[id << 1 | 1];
}

void update(int u, int v, int id = 1, int l = 1, int r = n) {
    if(u > r || v < l || st[id].mx == 0 || k == 1) return;
    if(l == r) {
        st[id].sum /= k;
        st[id].mx /= k;
        return;
    }
    int m = l + r >> 1;
    update(u, v, id << 1, l, m);
    update(u, v, id << 1 | 1, m + 1, r);
    st[id] = st[id << 1] + st[id << 1 | 1];
}

ll query(int u, int v, int id = 1, int l = 1, int r = n) {
    if(u > r || v < l) return 0;
    if(u <= l && r <= v) return st[id].sum;
    int m = l + r >> 1;
    return query(u, v, id << 1, l, m) + query(u, v, id << 1 | 1, m + 1, r);
}

void solve() {
     cin >> n >> q >> k;
     for(int i = 1, x; i <= n; ++i) {
        cin >> x;
        update_point(i, x);
     }
     while(q--) {
        int type, u, v; cin >> type >> u >> v;
        if(type == 1) update_point(u, v);
        if(type == 2) update(u, v);
        if(type == 3) cout << query(u, v) << '\n';
     }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

sterilizing.cpp: In function 'void update_point(int, int)':
sterilizing.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int m = l + r >> 1;
      |                 ~~^~~
sterilizing.cpp: In function 'void update(int, int, int, int, int)':
sterilizing.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int m = l + r >> 1;
      |             ~~^~~
sterilizing.cpp: In function 'long long int query(int, int, int, int, int)':
sterilizing.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3412 KB Output is correct
2 Correct 35 ms 4692 KB Output is correct
3 Correct 42 ms 6852 KB Output is correct
4 Correct 45 ms 6992 KB Output is correct
5 Correct 52 ms 7564 KB Output is correct
6 Correct 51 ms 7504 KB Output is correct
7 Correct 52 ms 7412 KB Output is correct
8 Correct 50 ms 7504 KB Output is correct
9 Correct 49 ms 7508 KB Output is correct
10 Correct 48 ms 7504 KB Output is correct
11 Correct 49 ms 7504 KB Output is correct
12 Correct 48 ms 7508 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2648 KB Output is correct
2 Correct 12 ms 2692 KB Output is correct
3 Correct 15 ms 2648 KB Output is correct
4 Correct 35 ms 2648 KB Output is correct
5 Correct 50 ms 4776 KB Output is correct
6 Correct 58 ms 4700 KB Output is correct
7 Correct 44 ms 5068 KB Output is correct
8 Correct 51 ms 6216 KB Output is correct
9 Correct 46 ms 6036 KB Output is correct
10 Correct 46 ms 5856 KB Output is correct
11 Correct 46 ms 5888 KB Output is correct
12 Correct 47 ms 5972 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2824 KB Output is correct
2 Correct 73 ms 2900 KB Output is correct
3 Correct 97 ms 2648 KB Output is correct
4 Correct 95 ms 2880 KB Output is correct
5 Correct 114 ms 4952 KB Output is correct
6 Correct 127 ms 4948 KB Output is correct
7 Correct 106 ms 4816 KB Output is correct
8 Correct 153 ms 4948 KB Output is correct
9 Correct 139 ms 5204 KB Output is correct
10 Correct 154 ms 4980 KB Output is correct
11 Correct 112 ms 5016 KB Output is correct
12 Correct 206 ms 4944 KB Output is correct