oj.uz

Submission #879010

# Submission time Handle Problem Language Result Execution time Memory
879010 2023-11-26T05:25:50 Z hafo Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 949 ms 8020 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 {
    struct node {
        ll sum;
        int mx, pos;
        friend node operator + (node a, const node &b) {
            if(a.mx == 0) a.mx = b.mx, a.pos = b.pos;
            a.sum += b.sum;
            return a;
        }

    };

    node st[4 * maxn];

    void build(int id, int l, int r) {
        if(l == r) {
            st[id] = {a[l], a[l], 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, val, l};
            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];
    }

    node get(int id, int l, int r, int u, int v) {
        if(r < u || l > v) return {0, 0, n + 1};
        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) {
            while(k > 1) {
                if(l > r) break;
                auto tmp = st.get(1, 1, n, l, r);
                if(tmp.mx == 0) break;
                st.update(1, 1, n, tmp.pos, tmp.mx / k);
                l = tmp.pos + 1; 
            }          
        }
        if(t == 3) {
            cout<<st.get(1, 1, n, l, r).sum<<"\n";
        }
    }
    return 0;
}

Compilation message

sterilizing.cpp: In member function 'void ST::build(int, int, int)':
sterilizing.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void ST::update(int, int, int, int, int)':
sterilizing.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
sterilizing.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5208 KB Output is correct
2 Correct 33 ms 4652 KB Output is correct
3 Correct 27 ms 6912 KB Output is correct
4 Correct 35 ms 7532 KB Output is correct
5 Correct 42 ms 8016 KB Output is correct
6 Correct 43 ms 8020 KB Output is correct
7 Correct 41 ms 7964 KB Output is correct
8 Correct 43 ms 8016 KB Output is correct
9 Correct 39 ms 7760 KB Output is correct
10 Correct 39 ms 7764 KB Output is correct
11 Correct 39 ms 7760 KB Output is correct
12 Correct 39 ms 7764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3164 KB Output is correct
2 Correct 15 ms 2908 KB Output is correct
3 Correct 19 ms 3040 KB Output is correct
4 Correct 46 ms 3956 KB Output is correct
5 Correct 64 ms 6484 KB Output is correct
6 Correct 64 ms 6480 KB Output is correct
7 Correct 38 ms 6504 KB Output is correct
8 Correct 64 ms 6480 KB Output is correct
9 Correct 65 ms 6736 KB Output is correct
10 Correct 60 ms 6224 KB Output is correct
11 Correct 60 ms 6228 KB Output is correct
12 Correct 60 ms 6224 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 4692 KB Output is correct
2 Correct 201 ms 4664 KB Output is correct
3 Correct 401 ms 4040 KB Output is correct
4 Correct 253 ms 4688 KB Output is correct
5 Correct 351 ms 7764 KB Output is correct
6 Correct 454 ms 7688 KB Output is correct
7 Correct 330 ms 7780 KB Output is correct
8 Correct 616 ms 7620 KB Output is correct
9 Correct 503 ms 7520 KB Output is correct
10 Correct 625 ms 7784 KB Output is correct
11 Correct 389 ms 7504 KB Output is correct
12 Correct 949 ms 7760 KB Output is correct