Submission #754928

#	Time	Username	Problem	Language	Result	Execution time	Memory
754928		definitelynotmee	Fish 2 (JOI22_fish2)	C++17	25 / 100	4050 ms	5468 KiB

fish2

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

const ll INFL = 1E18;
int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    vector<ll> in(n);

    for(ll & i : in)
        cin >> i;

    int q;
    cin >> q;

    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        if(t== 1){
            in[l] = r;
        } else {
            vector<ll> v(in.begin()+l,in.begin()+r);
            v.insert(v.begin(),INFL);
            v.push_back(INFL-1);

            int n = v.size();
            vector<int> jmp(n);
            vector<ll> psum(n);

            for(int i = 1; i < n; i++)
                psum[i] = psum[i-1]+v[i];

            vector<int> delta(n);

            auto make_ban =[&](int l, int r){
                if(v[r] > psum[r-1]-psum[l] && v[l] > psum[r-1]-psum[l] && l + 1 < r){
                    delta[l+1]++;
                    delta[r]--;
                }
            };

            for(int i = 1; i < n; i++){
                jmp[i] = i-1;
                while(v[jmp[i]] <= v[i]){
                    make_ban(jmp[i],i);
                    jmp[i] = jmp[jmp[i]];
                }
                if(i != n-1)
                    make_ban(jmp[i],i);
            }
            int resp = 0, cur = 0;
            for(int i = 1; i < n-1; i++){
                cur+=delta[i];
                if(cur == 0)
                    resp++;
            }
            cout << resp << '\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