// * Sigh *
#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, A[N], M[N], H[N];
vector < int > S[N];
inline bool CMP(int i, int j)
{
return (A[i] > A[j]);
}
inline bool Sub(int i, int j)
{
return ((i >> (H[i] - H[j])) == j);
}
inline bool Check(int i, int val)
{
return (Sub(i, M[val]));
}
int main()
{
scanf("%d", &n);
memset(A, 63, sizeof(A));
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]),
S[i].push_back(i);
for (int i = 1; i < N; i++)
H[i] = H[i >> 1] + 1;
for (int i = 1; i <= n; i++)
{
int lc = i << 1, rc = lc ^ 1;
sort(S[i].begin(), S[i].end(), CMP);
while (!Check(i, A[S[i].back()]))
S[i].pop_back();
printf("%d ", min({A[S[i].back()], A[lc], A[rc]}));
M[min({A[S[i].back()], A[lc], A[rc]})] = n + 1;
if (A[S[i].back()] < min(A[lc], A[rc]))
{
int id = S[i].back(), nw = i;
if (!Sub(i, id))
{
int p = id >> 1;
for (int a : S[p])
M[a] = max(M[a], id);
S[p].clear();
id ^= 1;
}
while (nw > id)
{
int p = nw >> 1;
for (int a : S[p])
M[a] = max(M[a], nw);
if (nw & 1)
M[A[nw^1]] = min(M[A[nw^1]], nw ^ 1);
S[p].clear(); nw >>= 1;
}
}
else if (A[lc] < A[rc])
S[lc] = S[i];
else
{
S[lc] = S[rc] = S[i];
S[lc].push_back(lc);
S[rc].push_back(lc);
}
}
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
swap.cpp:24:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i]),
~~~~~~~~~~~~~~~~~~^~
S[i].push_back(i);
~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
12800 KB |
Output is correct |
2 |
Correct |
15 ms |
12792 KB |
Output is correct |
3 |
Runtime error |
33 ms |
25468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
12800 KB |
Output is correct |
2 |
Correct |
15 ms |
12792 KB |
Output is correct |
3 |
Runtime error |
33 ms |
25468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
12800 KB |
Output is correct |
2 |
Correct |
15 ms |
12792 KB |
Output is correct |
3 |
Runtime error |
33 ms |
25468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
12800 KB |
Output is correct |
2 |
Correct |
15 ms |
12792 KB |
Output is correct |
3 |
Runtime error |
33 ms |
25468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
12800 KB |
Output is correct |
2 |
Correct |
15 ms |
12792 KB |
Output is correct |
3 |
Runtime error |
33 ms |
25468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |