Submission #1112676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112676		Zero_OP	Fish 2 (JOI22_fish2)	C++14	25 / 100	4070 ms	5044 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct segment_tree{
    vector<T> st;
    int n;

    segment_tree(int n) : n(n), st(n * 2 + 1) {}

    void update(int i, T v){
        st[i += n] = v;
        for(; i > 1; i >>= 1){
            st[i >> 1] = max(st[i], st[i ^ 1]);
        }
    }

    T query(int l, int r){
         l += n;
         r += n + 1;
         T res = {0, 0};

         for(; l < r; l >>= 1, r >>= 1){
            if(l & 1) res = max(res, st[l++]);
            if(r & 1) res = max(res, st[--r]);
         }
         return res;
    }
};

template<typename T>
struct fenwick_tree{
    vector<T> bit;
    static constexpr int offset = 1;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int id, T val){
        id += offset;
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += val;
        }
    }

    T query(int l, int r){
        T res(0);
        for(; l > 0; l -= l & (-l)) res -= bit[l];
        for(++r; r > 0; r -= r & (-r)) res += bit[r];
        return res;
    }
};

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

    int N;
    cin >> N;
    vector<int> a(N);
    segment_tree<pair<int, int>> st(N);
    fenwick_tree<long long> ft(N);

    for(int i = 0; i < N; ++i){
        cin >> a[i];
        st.update(i, {a[i], i});
        ft.update(i, a[i]);
    }

    function<int(int, int)> f = [&](int l, int r){
        if(l == r) return 1;

        int mx, pos;
        tie(mx, pos) = st.query(l, r);

        int ans = 1;
        if(l < pos && ft.query(l, pos - 1) >= mx) ans += f(l, pos - 1);
        if(pos < r && ft.query(pos + 1, r) >= mx) ans += f(pos + 1, r);
        return ans;
    };

    int Q;
    cin >> Q;
    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int i, v;
            cin >> i >> v;
            --i;
            st.update(i, {v, i});
            ft.update(i, -a[i] + v);
            a[i] = v;
        } else{
            int l, r;
            cin >> l >> r;
            --l, --r;
            cout << f(l, r) << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

fish2.cpp: In instantiation of 'segment_tree<T>::segment_tree(int) [with T = std::pair<int, int>]':
fish2.cpp:60:38:   required from here
fish2.cpp:8:9: warning: 'segment_tree<std::pair<int, int> >::n' will be initialized after [-Wreorder]
    8 |     int n;
      |         ^
fish2.cpp:7:15: warning:   'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > segment_tree<std::pair<int, int> >::st' [-Wreorder]
    7 |     vector<T> st;
      |               ^~
fish2.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     segment_tree(int n) : n(n), st(n * 2 + 1) {}
      |     ^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17