Submission #711943

#	Time	Username	Problem	Language	Result	Execution time	Memory
711943		kostia244	Fish 2 (JOI22_fish2)	C++17	25 / 100	4075 ms	4452 KiB

fish2

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int inf = 1'000'000'003;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) cin >> i;
    
    auto get_sum = [&](int a, int b) {
        return min(a + b, inf);
    };
 
    vector<int> die(n + 1);
    vector<array<int, 3>> useful;
    auto add = [&](int l, int r) {
        if(l < r) {
            die[l]++;
            die[r]--;
        }
    };
 
    auto scan = [&](vector<array<int, 3>> ind, int mode) {
        vector<array<ll, 3>> st;
        for(auto [i, ls, rs] : ind) {
            int sum = ls;
            while(st.size() && a[st.back()[0]] < a[i]) {
                sum = get_sum(sum, get_sum(st.back()[1], a[st.back()[0]]));
                st.pop_back();
            }
            if(sum < a[i]) {
                if(mode == 0) {//fwd
                    add(st.empty() ? ind[0][0] : st.back()[0] + 1, i);
                } else {
                    add(i + 1, st.empty() ? ind[0][0] + 1 : st.back()[0]);
                }
            }
            st.push_back({i, sum});
        }
    };
 
    cin >> q;
    for(int t, l, r, i = 0; i < q; i++) {
        cin >> t >> l >> r;
        --l;
        if(t == 1) {
            a[l] = r;
        } else {
            useful.clear();
            for(int i = l; i < r; i++)
                die[i] = 0, useful.push_back({i, 0, 0});
            
            scan(useful, 0);
            reverse(all(useful));
            for(auto &[i, ls, rs] : useful)
                swap(ls, rs);
            scan(useful, 1);
            
 
            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