Untitled

 avatar
unknown
plain_text
a year ago
3.1 kB
4
Indexable


void solve () {
    int n; cin>>n;
    vi arr (n+1); for (int i=1; i<=n; i++) cin>>arr[i];

    vi prevuniqueidx (n+1, -1), nextuniqueidx (n+1, -1);
    vi temp; //max two len :P

    for (int i=1; i<=n; i++) {
        if (temp.size()<2) prevuniqueidx[i] = -1;
        else prevuniqueidx[i] = temp[0];

        if (temp.size()==0) {
            temp.pb(i);
        }
        else if (temp.size()==1) {
            if (arr[temp[0]]==arr[i]) ;
            else temp.pb(i);
        }
        else {
            if (arr[temp[1]]==arr[i]) temp[1] = i;
            else if (arr[temp[0]]==arr[i]) {
                temp[0] = temp[1];
                temp[1] = i;
            }
            else {
                temp[0] = temp[1];
                temp[1] = i;
            }
        }
    }

    vi prefsum (n+1, 0);
    for (int i=1; i<=n; i++) {
        prefsum[i] = prefsum[i-1] + arr[i];
    }

    vi suffsum (n+2, 0);
    for (int i=n; i>=1; i--) {
        suffsum[i] = suffsum[i+1] + arr[i];
    }

    vi ans (n+1,LLONG_MAX);

    for (int i=1; i<=n; i++) {
        if (i!=1 && arr[i-1]>arr[i]) {
            ans[i] = 1;
            continue;
        }

        int low=1, high=prevuniqueidx[i];
        if (high<low) continue;

        int lookfor = prefsum[i-1] - arr[i];

        auto it = lower_bound (prefsum.begin()+low, prefsum.begin()+high, lookfor);
        int idx = it - prefsum.begin();

        for (int j=max(low,idx-3); j<=min(high,idx+3); j++) {
            if (prefsum[j-1]<lookfor) {
                ans[i] = min (ans[i], i-j);
            }
        }
    }
    



    temp.clear();
    reverse(arr.begin()+1, arr.end());

    prevuniqueidx.resize(n+1,-1);
    prefsum.resize(n+1,0);

    for (int i=1; i<=n; i++) {
        prefsum[i] = prefsum[i-1] + arr[i];
    }

    for (int i=1; i<=n; i++) {
        if (temp.size()<2) prevuniqueidx[i] = -1;
        else prevuniqueidx[i] = temp[0];

        if (temp.size()==0) {
            temp.pb(i);
        }
        else if (temp.size()==1) {
            if (arr[temp[0]]==arr[i]) ;
            else temp.pb(i);
        }
        else {
            if (arr[temp[1]]==arr[i]) temp[1] = i;
            else if (arr[temp[0]]==arr[i]) {
                temp[0] = temp[1];
                temp[1] = i;
            }
            else {
                temp[0] = temp[1];
                temp[1] = i;
            }
        }
    }

    
    for (int i=1; i<=n; i++) {
        if (i!=1 && arr[i-1]>arr[i]) {
            ans[n+1-i] = 1;
            continue;
        }

        int low=1, high=prevuniqueidx[i];
        if (high<low) continue;

        int lookfor = prefsum[i-1] - arr[i];

        auto it = lower_bound (prefsum.begin()+low, prefsum.begin()+high, lookfor);
        int idx = it - prefsum.begin();

        for (int j=max(low,idx-3); j<=min(high,idx+3); j++) {
            if (prefsum[j-1]<lookfor) {
                ans[n+1-i] = min (ans[n+1-i], i-j);
            }
        }
    }


    for (int &x: ans) if (x==LLONG_MAX) x=-1;

    for (int i=1; i<=n; i++) cout << ans[i] << " ";
    cout << "\n";

    

}
Editor is loading...
Leave a Comment