Submission #1029709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029709		Otalp	Fish 2 (JOI22_fish2)	C++17	13 / 100	4088 ms	8392 KiB

fish2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

int a[200100];
ll pref[200100];
int ok[200100];

void solve(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        pref[i] = pref[i - 1]  + a[i];
    }
    int t;
    cin>>t;
    while(t--){
        int c;
        cin>>c;
        if(c == 1){
            int x, y;
            cin>>x>>y;
            a[x] = y;
            for(int i=1; i<=n; i++){
                pref[i] = pref[i - 1] + a[i];
            }
        }
        else{
            int l, r;
            cin>>l>>r;
            set<int> pos;
            vector<pii> d;
            int mx = 0;
            for(int i=l; i<=r; i++){
                d.pb({a[i], i});
                ok[i] = 0;
                mx = max(a[i], mx);
            }
            sort(d.begin(), d.end(), greater<pii>());
            for(pii h: d){
                if(h.ff == mx){
                    ok[h.ss] = 1;
                    pos.insert(h.ss);
                    continue;
                }
                int L, R;
                auto it = pos.lower_bound(h.ss);
                if(it == pos.begin()){
                    L = l;
                }
                else{
                    it--;
                    L = *it + 1;
                    it++;
                }
                if(it == pos.end()){
                    R = r;
                }
                else{
                    R = *it - 1;
                }
                ll sum = pref[R] - pref[L - 1];
                if(L > l and ok[L-1] and sum >= a[L-1]) ok[h.ss] = 1;
                if(R < r and ok[R+1] and sum >= a[R+1]) ok[h.ss] = 1;
                pos.insert(h.ss);
            }
            int res = 0;
            for(int i=l; i<=r; i++) res += ok[i];
            cout<<res<<'\n';
        }
    }





            
                

}

signed main(){
    solve();
}

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