Untitled
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