# Untitled

unknown
plain_text
2 months ago
3.1 kB
0
Indexable
Never
```

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";

}```