#include <stdio.h>
int ans[500005], arr[500005];
int it[1100000], loc[1100000];
int maxi, t=1, l;
void max_it(int ns, int ne, int s, int e, int now) {
if (e < ns || ne < s) return;
if (ns <= s && e <= ne) {
if (maxi < it[now]) {
maxi = it[now];
l = loc[now];
}
return;
}
max_it(ns, ne, s, (s + e) / 2, now * 2);
max_it(ns, ne, (s + e) / 2 + 1, e, now * 2 + 1);
}
int fd(int s, int e, int val)
{
int left, right;
while (s!=e) {
//printf("1\n");
maxi = 0;
max_it(s, (s + e) / 2, 1, t, 1);
left = maxi;
if (val < left) e = (s + e) / 2;
else {
s = (s + e) / 2 + 1;
}
}
return s;
}
int main()
{
int n, i, j, p, now, next, flag = 0, le, ri, k, v;
scanf("%d", &n);
while (1) {
if (t > n) break;
t = t * 2;
}
for (i = t; i < t+n; i++) {
scanf("%d", &it[i]);
p = i / 2;
loc[i] = i - t + 1;
while (p > 0) {
if (it[p] < it[i]) {
it[p] = it[i];
loc[p] = i - t + 1;
}
p = p / 2;
}
}
for (i = 1; i <= n; i++) {
//printf("%d\n", i);
if (flag == 1 || i == n) {
ans[i] = -1;
continue;
}
maxi = 0;
max_it(1, i, 1, t, 1);
now = maxi, le = l;
for (j = i + 1; j <= n; j = j + i) {
maxi = 0;
max_it(j, j + i - 1, 1, t, 1);
next = maxi, ri = l;
//printf("%d %d\n", le, ri);
if (now < next) {
ans[i]=fd(j, j + i - 1, now)-i;
break;
}
else if (now == next && ri - le > i) {
for (k = j; k < j + i; k++) {
maxi = 0;
max_it(k - i, k - 1, 1, t, 1);
if (maxi < it[k + t - 1]) {
ans[i] = k - i;
break;
}
}
if (k < j + i) break;
}
now = next;
}
if (j > n) {
ans[i] = -1;
flag = 1;
}
}
for (i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}
Compilation message
box.cpp: In function 'int fd(int, int, int)':
box.cpp:19:12: warning: unused variable 'right' [-Wunused-variable]
int left, right;
^~~~~
box.cpp: In function 'int main()':
box.cpp:34:50: warning: unused variable 'v' [-Wunused-variable]
int n, i, j, p, now, next, flag = 0, le, ri, k, v;
^
box.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
box.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &it[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Correct |
5 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
508 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
552 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
356 KB |
Output is correct |
| 3 |
Correct |
5 ms |
432 KB |
Output is correct |
| 4 |
Correct |
3 ms |
508 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
552 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
