Submission #711933

#	Time	Username	Problem	Language	Result	Execution time	Memory
711933		kostia244	Fish 2 (JOI22_fish2)	C++17	25 / 100	4035 ms	2080 KiB

fish2

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) cin >> i;
    cin >> q;
    for(int t, l, r, i = 0; i < q; i++) {
        cin >> t >> l >> r;
        --l;
        if(t == 1) {
            a[l] = r;
        } else {
            vector<int> die(n + 1);
            auto add = [&](int l, int r) {
                if(l < r) {
                    die[l]++;
                    die[r]--;
                }
            };

            vector<array<ll, 2>> st;//{right, sum, blocked}
            for(int i = l; i < r; i++) {
                ll sum = 0;
                while(st.size() && a[st.back()[0]] < a[i]) {
                    sum += st.back()[1] + a[st.back()[0]];
                    st.pop_back();
                }
                if(sum < a[i]) {
                    add(st.empty() ? l : st.back()[0] + 1, i);
                }
                st.push_back({i, sum});
            }

            st.clear();//{right, sum, blocked}
            for(int i = r; i-- > l;) {
                ll sum = 0;
                while(st.size() && a[st.back()[0]] < a[i]) {
                    sum += st.back()[1] + a[st.back()[0]];
                    st.pop_back();
                }
                if(sum < a[i]) {//[i + 1; st.back())
                    add(i + 1, st.empty() ? n : st.back()[0]);
                }
                st.push_back({i, sum});
            }//6 4 1 2 6

            int ans = 0, cur = 0;
            for(int i = l; i < r; i++) {
                cur += die[i];
                ans += !cur;
            }
            cout << ans << '\n';
        }
    }
}

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