oj.uz

Submission #879011

# Submission time Handle Problem Language Result Execution time Memory
879011 2023-11-26T05:31:26 Z hafo Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 129 ms 5468 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, q, k, t, l, r, a[maxn];

struct ST {
    ll st[4 * maxn];

    void build(int id, int l, int r) {
        if(l == r) {
            st[id] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update(int id, int l, int r, int pos, int val) {
        if(pos < l || pos > r) return;
        if(l == r) {
            st[id] = val;
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update2(int id, int l, int r, int u, int v) {
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            if(st[id] == 0) return;

            if(l == r) {
                st[id] /= k;
                return;
            }
        }
        int mid = l + r >> 1;
        update2(id << 1, l, mid, u, v);
        update2(id << 1 | 1, mid + 1, r, u, v);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    ll get(int id, int l, int r, int u, int v) {
        if(r < u || l > v) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }

} st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q>>k;
    for(int i = 1; i <= n; i++) cin>>a[i];

    st.build(1, 1, n);
    while(q--) {
        cin>>t>>l>>r;
        if(t == 1) {
            st.update(1, 1, n, l, r);
        } 
        if(t == 2) {
            if(k > 1) {
                st.update2(1, 1, n, l, r);
            }          
        }
        if(t == 3) {
            cout<<st.get(1, 1, n, l, r)<<"\n";
        }
    }
    return 0;
}

Compilation message

sterilizing.cpp: In member function 'void ST::build(int, int, int)':
sterilizing.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void ST::update(int, int, int, int, int)':
sterilizing.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void ST::update2(int, int, int, int, int)':
sterilizing.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'long long int ST::get(int, int, int, int, int)':
sterilizing.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2548 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2556 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 3 ms 2512 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 2584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5200 KB Output is correct
2 Correct 30 ms 4956 KB Output is correct
3 Correct 25 ms 5212 KB Output is correct
4 Correct 33 ms 5412 KB Output is correct
5 Correct 40 ms 5456 KB Output is correct
6 Correct 39 ms 5460 KB Output is correct
7 Correct 41 ms 5468 KB Output is correct
8 Correct 40 ms 5428 KB Output is correct
9 Correct 37 ms 5456 KB Output is correct
10 Correct 37 ms 5460 KB Output is correct
11 Correct 45 ms 5468 KB Output is correct
12 Correct 36 ms 5376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2652 KB Output is correct
2 Correct 9 ms 4848 KB Output is correct
3 Correct 14 ms 4700 KB Output is correct
4 Correct 40 ms 4768 KB Output is correct
5 Correct 47 ms 4956 KB Output is correct
6 Correct 48 ms 4956 KB Output is correct
7 Correct 35 ms 5204 KB Output is correct
8 Correct 47 ms 4956 KB Output is correct
9 Correct 44 ms 4952 KB Output is correct
10 Correct 43 ms 5112 KB Output is correct
11 Correct 41 ms 4956 KB Output is correct
12 Correct 45 ms 4952 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5024 KB Output is correct
2 Correct 57 ms 4924 KB Output is correct
3 Correct 59 ms 4944 KB Output is correct
4 Correct 74 ms 5460 KB Output is correct
5 Correct 82 ms 5316 KB Output is correct
6 Correct 88 ms 5332 KB Output is correct
7 Correct 78 ms 5164 KB Output is correct
8 Correct 112 ms 5440 KB Output is correct
9 Correct 90 ms 5156 KB Output is correct
10 Correct 100 ms 5160 KB Output is correct
11 Correct 86 ms 5200 KB Output is correct
12 Correct 129 ms 5200 KB Output is correct