Submission #905163

#	Time	Username	Problem	Language	Result	Execution time	Memory
905163		Ahmed57	Fish 2 (JOI22_fish2)	C++17	13 / 100	4049 ms	9404 KiB

fish2

//#include "dango3.h"
 
#include <bits/stdc++.h>
using namespace std;
int logg[100001],sp[100001][17];
int get(int l,int r){
    int sz = r-l+1;
    int lo = logg[sz];
    return max(sp[l][lo],sp[r-(1<<lo)+1][lo]);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n;
    cin>>n;
    long long arr[n+1],pref[n+1] = {0};
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        sp[i][0] = arr[i];
        pref[i] = arr[i]+pref[i-1];
    }
    logg[1] = 0;
    for(int i = 2;i<=n;i++){
        logg[i] = logg[i/2]+1;
    }
    for(int i = n;i>=1;i--){
        for(int j = 1;j<17;j++){
            if(i+(1<<j)-1<=n){
                sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int q;cin>>q;
    bool update = 0;
    while(q--){
    int ty,LL,RR;cin>>ty>>LL>>RR;
    if(ty==1){
        arr[LL] = RR;
        update = 1;
        continue;
    }
    if(update){
        update = 0;
        for(int i = 1;i<=n;i++){
            pref[i] = arr[i]+pref[i-1];
            sp[i][0] = arr[i];
        }
        for(int i = n;i>=1;i--){
            for(int j = 1;j<17;j++){
                if(i+(1<<j)-1<=n){
                    sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    int fin = 0;
    for(int i = LL;i<=RR;i++){
        int cnt = 0;
        long long l = i , r = i , sum = 0;
        bool ss = 0;
        while(cnt<=1){
            sum = pref[r]-pref[l-1];
            if(ss==0){
                int L = LL , R = l-1 , ans = l;
                while(L<=R){
                    int mid = (L+R)/2;
                    if(get(mid,l-1)<=sum){
                        ans = mid;
                        R = mid-1;
                    }else L = mid+1;
                }
                if(l==ans){
                    cnt++;
                }else{
                    l = ans;
                    cnt = 0;
                }
            }else{
                int L = r+1 , R = RR , ans = r;
                while(L<=R){
                    int mid = (L+R)/2;
                    if(get(r+1,mid)<=sum){
                        ans = mid;
                        L = mid+1;
                    }else R = mid-1;
                }
                if(r==ans){
                    cnt++;
                }else{
                    r = ans;
                    cnt = 0;
                }
            }
            ss = !ss;
        }
        if(l==LL&&r==RR){
            fin++;
        }
    }
    cout<<fin<<endl;
}
}

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