#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int seg[2000000];
int a[500100],ch[500100],dap[500100];
vector<int> vt;
int getidx(int x) {
return lower_bound(vt.begin(), vt.end(), x) - vt.begin();
}
int update(int pos, int val, int node, int x, int y)
{
if (pos < x || pos > y)return seg[node];
if (x == y)return seg[node] = max(val, seg[node]);
int mid = (x + y) / 2;
return seg[node] = max(update(pos, val, node * 2, x, mid), update(pos, val, node * 2 + 1, mid + 1, y));
}
int query(int lo, int hi, int node, int x, int y)
{
if (hi < x || y < lo)return 0;
if (lo <= x&&y <= hi)return seg[node];
int mid = (x + y) / 2;
return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
vt.push_back(a[i]);
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());
for (int i = 1; i <= n; i++)
a[i] = getidx(a[i]);
int t = vt.size();
for (int i = 1; i <= n; i++)
{
if (a[i] !=t - 1)
ch[i] = query(a[i] + 1, n - 1, 1, 0, t - 1);
update(a[i], i, 1, 0, t - 1);
}
int prev = 0;
for (int i = 2; i <= n; i++)
{
if (i - ch[i]-1 > prev)
{
for (int y = prev + 1; y <= i - ch[i]-1; y++)
dap[y] = i - y;
prev = i - ch[i]-1;
}
}
for (int i = 1; i <= n; i++) {
if (dap[i])
printf("%d ", dap[i]);
else
printf("-1 ");
}
}
Compilation message
box.cpp: In function 'int main()':
box.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
box.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
560 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
560 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
