Submit Info #21105

Problem Lang User Status Time Memory
Cartesian Tree cpp (anonymous) AC 157 ms 18.67 MiB

ケース詳細
Name Status Time Memory
almost-decreasing_00 AC 147 ms 14.80 MiB
almost-decreasing_01 AC 71 ms 7.17 MiB
almost-increasing_00 AC 151 ms 18.67 MiB
almost-increasing_01 AC 72 ms 8.92 MiB
decreasing_00 AC 147 ms 14.80 MiB
decreasing_01 AC 70 ms 7.17 MiB
example_00 AC 1 ms 0.62 MiB
example_01 AC 1 ms 0.67 MiB
increasing_00 AC 153 ms 18.66 MiB
increasing_01 AC 71 ms 8.92 MiB
random_00 AC 157 ms 14.80 MiB
random_01 AC 75 ms 7.17 MiB
random_02 AC 92 ms 8.87 MiB
random_03 AC 70 ms 6.67 MiB
random_04 AC 128 ms 12.05 MiB
small_00 AC 1 ms 0.62 MiB
small_01 AC 1 ms 0.64 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 1 ms 0.61 MiB
small_06 AC 1 ms 0.67 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 1 ms 0.66 MiB
small_09 AC 1 ms 0.65 MiB

#pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4") #include <bits/stdc++.h> using namespace std; constexpr int N = 1 << 20; int a[N], p[N], stk[N]; int main() { // freopen("input.txt", "r", stdin); int n; scanf("%d", &n); memset(p, -1, n << 2); for (int i = 0; i < n; ++i) { scanf("%d", a + i); } for (int i = 0, sz = 0; i < n; ++i) { int last = -1; while (sz && a[stk[sz]] > a[i]) { p[last = stk[sz]] = sz > 1 ? stk[sz - 1] : i; --sz; } if (~last) { p[last] = i; } if (sz) { p[i] = stk[sz]; } stk[++sz] = i; } for (int i = 0; i < n; ++i) { printf("%d%c", ~p[i] ? p[i] : i, i == n - 1 ? '\n' : ' '); } return 0; }