Submission #1690744
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int N = 202020;
inline char get(void) {
static char buf[100000], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, 100000, stdin);
if (S == T) return EOF;
}
return *S++;
}
template<typename T>
inline void read(T &x) {
static char c; x = 0; int sgn = 0;
for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
if (sgn) x = -x;
}
int a[N];
int n, l, r;
struct Seg {
int c[N];
int mn[N << 2];
inline int MinPos(int a, int b) {
return c[a] < c[b] ? a : b;
}
inline void Build(int o, int l, int r) {
if (l == r) return (void)(mn[o] = l);
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
mn[o] = MinPos(mn[o << 1], mn[o << 1 | 1]);
}
inline void Init(int fl) {
for (int i = 0; i <= n; i++) c[i] = N;
for (int i = fl; i <= n; i += 2)
c[i] = a[i];
Build(1, 1, n);
}
inline int MinPos(int o, int l, int r, int L, int R) {
if (l >= L && r <= R) return mn[o];
int mid = (l + r) >> 1, res = 0;
if (L <= mid) res = MinPos(res, MinPos(o << 1, l, mid, L, R));
if (R > mid) res = MinPos(res, MinPos(o << 1 | 1, mid + 1, r, L, R));
return res;
}
};
Seg S[2];
struct cpp {
int l, r, s, t, fl;
cpp(void) {}
cpp(int _l, int _r, int f) {
l = _l; r = _r; fl = f;
s = S[fl].MinPos(1, 1, n, l, r);
t = S[fl ^ 1].MinPos(1, 1, n, s, r);
}
inline bool operator <(const cpp &x) const{
return a[s] > a[x.s];
}
};
cpp x;
priority_queue<cpp> Q;
int main(void) {
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
S[1].Init(1); S[0].Init(2);
Q.push(cpp(1, n, 1));
while (!Q.empty()) {
x = Q.top(); Q.pop();
printf("%d %d ", a[x.s], a[x.t]);
if (x.l < x.s) Q.push(cpp(x.l, x.s - 1, x.fl));
if (x.t < x.r) Q.push(cpp(x.t + 1, x.r, x.fl));
if (x.s + 1 < x.t) Q.push(cpp(x.s + 1, x.t - 1, x.fl ^ 1));
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Young Maids |
User |
Vectorxj |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
2015 Byte |
Status |
AC |
Exec Time |
106 ms |
Memory |
11252 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
3 ms |
6400 KB |
0_01.txt |
AC |
2 ms |
6400 KB |
0_02.txt |
AC |
2 ms |
6400 KB |
1_00.txt |
AC |
2 ms |
6400 KB |
1_01.txt |
AC |
2 ms |
6400 KB |
1_02.txt |
AC |
54 ms |
10240 KB |
1_03.txt |
AC |
52 ms |
10240 KB |
1_04.txt |
AC |
73 ms |
10240 KB |
1_05.txt |
AC |
98 ms |
11124 KB |
1_06.txt |
AC |
101 ms |
11000 KB |
1_07.txt |
AC |
100 ms |
11252 KB |
1_08.txt |
AC |
99 ms |
11000 KB |
1_09.txt |
AC |
53 ms |
10240 KB |
1_10.txt |
AC |
73 ms |
10240 KB |
1_11.txt |
AC |
66 ms |
10240 KB |
1_12.txt |
AC |
97 ms |
10872 KB |
1_13.txt |
AC |
102 ms |
11000 KB |
1_14.txt |
AC |
97 ms |
11000 KB |
1_15.txt |
AC |
99 ms |
11000 KB |
1_16.txt |
AC |
106 ms |
11000 KB |
1_17.txt |
AC |
100 ms |
11000 KB |
1_18.txt |
AC |
100 ms |
11000 KB |
1_19.txt |
AC |
98 ms |
11000 KB |