#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef CB
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
vector<int> a(N);
vector<int> b(N);
for (int i = 1; i <= N - 2; i++) {
a[i] = lower_bound(v.begin(), v.end(), v[i] * 2 - v[i - 1]) - v.begin() - 1;
b[i] = lower_bound(v.begin(), v.end(), v[i] * 2 - v[i + 1]) - v.begin();
}
vector<array<int, 20>> spt(N);
for (int i = 0; i < N; i++) {
spt[i][0] = a[i];
}
for (int j = 1; j < 20; j++) {
for (int l = 0, r = 1 << j - 1; r < N; l++, r++) {
spt[l][j] = max(spt[l][j - 1], spt[r][j - 1]);
}
}
auto query = [&](int l, int r) -> int {
if (l == r) {
return -1;
}
int i = __lg(r - l);
return max(spt[l][i], spt[r - (1 << i)][i]);
};
vector<int> ans(N);
ans[0] = N - 1;
ans[N - 1] = 0;
vector<int> s;
for (int i = N - 2; i >= 1; i--) {
while (!s.empty() && b[s.back()] >= b[i]) {
s.pop_back();
}
s.push_back(i);
ans[i] = N - 1;
int x = query(0, b[s.front()] + 1);
if (x > s.front()) {
ans[i] = 0;
continue;
}
if (b[s.front()] == i) {
ans[i] = 0;
continue;
}
for (int j = 1; j < s.size(); j++) {
int y = query(b[s.front()] + 1, b[s[j]] + 1);
if (j + 1 < s.size() && query(b[s[j]] + 1, b[s[j + 1]] + 1) <= s[j + 1]) {
continue;
}
if (y <= s[j] && x > s[j]) {
ans[i] = 0;
break;
}
}
}
for (int i = 0; i < N; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1828 KiB | ||||
2 | Accepted | 3ms | 2024 KiB | ||||
subtask2 | 12/12 | ||||||
3 | Accepted | 2ms | 2100 KiB | ||||
4 | Accepted | 3ms | 2240 KiB | ||||
5 | Accepted | 3ms | 2448 KiB | ||||
6 | Accepted | 3ms | 2676 KiB | ||||
7 | Accepted | 3ms | 2876 KiB | ||||
8 | Accepted | 3ms | 3108 KiB | ||||
9 | Accepted | 3ms | 3032 KiB | ||||
10 | Accepted | 2ms | 3116 KiB | ||||
11 | Accepted | 3ms | 3216 KiB | ||||
12 | Accepted | 3ms | 3092 KiB | ||||
subtask3 | 0/28 | ||||||
13 | Accepted | 3ms | 3360 KiB | ||||
14 | Accepted | 3ms | 3392 KiB | ||||
15 | Accepted | 3ms | 3192 KiB | ||||
16 | Accepted | 3ms | 3196 KiB | ||||
17 | Accepted | 3ms | 3200 KiB | ||||
18 | Accepted | 3ms | 3200 KiB | ||||
19 | Accepted | 3ms | 3600 KiB | ||||
20 | Wrong answer | 3ms | 3488 KiB | ||||
21 | Accepted | 3ms | 3488 KiB | ||||
subtask4 | 35/35 | ||||||
22 | Accepted | 74ms | 40648 KiB | ||||
23 | Accepted | 82ms | 40836 KiB | ||||
24 | Accepted | 74ms | 41096 KiB | ||||
25 | Accepted | 72ms | 40864 KiB | ||||
26 | Accepted | 41ms | 25016 KiB | ||||
27 | Accepted | 65ms | 40896 KiB | ||||
28 | Accepted | 65ms | 40832 KiB | ||||
29 | Accepted | 65ms | 40856 KiB | ||||
30 | Accepted | 67ms | 40856 KiB | ||||
31 | Accepted | 74ms | 40836 KiB | ||||
subtask5 | 0/25 | ||||||
32 | Time limit exceeded | 1.024s | 378884 KiB | ||||
33 | Accepted | 776ms | 341392 KiB | ||||
34 | Time limit exceeded | 1.031s | 379152 KiB | ||||
35 | Wrong answer | 768ms | 341528 KiB | ||||
36 | Wrong answer | 981ms | 363744 KiB | ||||
37 | Accepted | 801ms | 379868 KiB | ||||
38 | Accepted | 934ms | 372252 KiB | ||||
39 | Accepted | 802ms | 379816 KiB | ||||
40 | Accepted | 957ms | 379624 KiB | ||||
41 | Time limit exceeded | 1.034s | 378608 KiB | ||||
42 | Accepted | 795ms | 365448 KiB | ||||
43 | Accepted | 977ms | 374196 KiB | ||||
44 | Time limit exceeded | 1.021s | 378660 KiB | ||||
45 | Accepted | 842ms | 377124 KiB | ||||
46 | Accepted | 829ms | 377116 KiB | ||||
47 | Time limit exceeded | 1.072s | 191604 KiB | ||||
48 | Time limit exceeded | 1.077s | 191596 KiB | ||||
49 | Time limit exceeded | 1.072s | 191372 KiB | ||||
50 | Time limit exceeded | 1.075s | 191460 KiB |