Submit Info #21108

Problem Lang User Status Time Memory
Cartesian Tree cpp (anonymous) AC 43 ms 18.80 MiB

ケース詳細
Name Status Time Memory
almost-decreasing_00 AC 33 ms 14.92 MiB
almost-decreasing_01 AC 15 ms 7.25 MiB
almost-increasing_00 AC 36 ms 18.74 MiB
almost-increasing_01 AC 16 ms 9.05 MiB
decreasing_00 AC 33 ms 14.92 MiB
decreasing_01 AC 15 ms 7.30 MiB
example_00 AC 1 ms 0.67 MiB
example_01 AC 0 ms 0.67 MiB
increasing_00 AC 40 ms 18.80 MiB
increasing_01 AC 19 ms 9.12 MiB
random_00 AC 43 ms 15.05 MiB
random_01 AC 21 ms 7.30 MiB
random_02 AC 26 ms 8.99 MiB
random_03 AC 19 ms 6.80 MiB
random_04 AC 35 ms 12.11 MiB
small_00 AC 3 ms 0.62 MiB
small_01 AC 1 ms 0.69 MiB
small_02 AC 1 ms 0.60 MiB
small_03 AC 3 ms 0.66 MiB
small_04 AC 2 ms 0.67 MiB
small_05 AC 0 ms 0.62 MiB
small_06 AC 1 ms 0.62 MiB
small_07 AC 2 ms 0.67 MiB
small_08 AC 1 ms 0.65 MiB
small_09 AC 1 ms 0.67 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; /** Fast input-output */ template <class T = int> inline T readInt(); inline double readDouble(); inline int readUInt(); inline int readChar(); // first non-blank character inline void readWord( char *s ); inline bool readLine( char *s ); // do not save '\n' inline bool isEof(); inline int getChar(); inline int peekChar(); inline bool seekEof(); inline void skipBlanks(); template <class T> inline void writeInt( T x, char end = 0, int len = -1 ); inline void writeChar( int x ); inline void writeWord( const char *s ); inline void flush(); static struct buffer_flusher_t { ~buffer_flusher_t() { flush(); } } buffer_flusher; /** Read */ static const int buf_size = 1 << 16; static unsigned char buf[buf_size]; static int buf_len = 0, buf_pos = 0; inline bool isEof() { if (buf_pos == buf_len) { buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin); if (buf_pos == buf_len) return 1; } return 0; } inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; } inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; } inline bool seekEof() { int c; while ((c = peekChar()) != -1 && c <= 32) buf_pos++; return c == -1; } inline void skipBlanks() { while (!isEof() && buf[buf_pos] <= 32U) buf_pos++; } inline int readChar() { int c = getChar(); while (c != -1 && c <= 32) c = getChar(); return c; } inline int readUInt() { int c = readChar(), x = 0; while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return x; } template <class T> inline T readInt() { int s = 1, c = readChar(); T x = 0; if (c == '-') s = -1, c = getChar(); else if (c == '+') c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return s == 1 ? x : -x; } inline double readDouble() { int s = 1, c = readChar(); double x = 0; if (c == '-') s = -1, c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); if (c == '.') { c = getChar(); double coef = 1; while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar(); } return s == 1 ? x : -x; } inline void readWord( char *s ) { int c = readChar(); while (c > 32) *s++ = c, c = getChar(); *s = 0; } inline bool readLine( char *s ) { int c = getChar(); while (c != '\n' && c != -1) *s++ = c, c = getChar(); *s = 0; return c != -1; } /** Write */ static int write_buf_pos = 0; static char write_buf[buf_size]; inline void writeChar( int x ) { if (write_buf_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0; write_buf[write_buf_pos++] = x; } inline void flush() { if (write_buf_pos) { fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0; fflush(stdout); } } template <class T> inline void writeInt( T x, char end, int output_len ) { char s[8]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n--) writeChar(s[n]); if (end) writeChar(end); } inline void writeWord( const char *s ) { while (*s) writeChar(*s++); } constexpr int N = 1 << 20, N1 = N - 1; int a[N], p[N], stk[N]; int main() { // freopen("input.txt", "r", stdin); int n = readInt(); memset(p, -1, n << 2); for (int i = 0; i < n; ++i) { a[i] = readInt(); } for (int i = 0, sz = N; i < n; ++i) { int last = -1; while (sz < N && a[stk[sz]] > a[i]) { p[last = stk[sz]] = sz < N1 ? stk[sz + 1] : i; ++sz; } ~last && (p[last] = i); (sz < N) && (p[i] = stk[sz]); stk[--sz] = i; } for (int i = 0; i < n; ++i) { writeInt(~p[i] ? p[i] : i, i == n - 1 ? '\n' : ' '); } return 0; }