Submission #1488570

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <set>
#include <utility>
static const int MAXN = 2e5 + 4;

int n;
int a[MAXN], p[MAXN];
int b[MAXN], top = 0;

struct rmq {
    static const int LOGN = 18;
    std::pair<int, int> f[LOGN][MAXN];
    inline void build(int n, int *a) {
        for (int i = 0; i < n; ++i) f[0][i] = std::make_pair(a[i], i);
        for (int j = 1; j < LOGN; ++j)
            for (int i = 0; i <= n - (1 << j); ++i)
                f[j][i] = std::min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
    }
    inline std::pair<int, int> query(int l, int r) {
        if (l == r) return f[0][l];
        int sz = 8 * sizeof(int) - __builtin_clz(r - l) - 1;
        return std::min(f[sz][l], f[sz][r - (1 << sz) + 1]);
    }
} all, even, odd;

struct cmp_peek {
    inline bool operator ()(const std::pair<int, int> a, const std::pair<int, int> b)
    {
        int ua = ((a.first & 1) ? odd : even).query(a.first, a.second).first;
        int ub = ((b.first & 1) ? odd : even).query(b.first, b.second).first;
        return ua < ub;
    }
};

std::set<std::pair<int, int>, cmp_peek> s;

void solve(int l, int r)
{
    auto u = ((l & 1) ? odd : even).query(l, r);
    auto v = ((r & 1) ? odd : even).query(l, r);
    int pu = u.second, pv = v.second;
    b[top++] = u.first;
    b[top++] = v.first;
    if (l <= pu - 1) s.insert(std::make_pair(l, pu - 1));
    if (pu + 1 <= pv - 1) s.insert(std::make_pair(pu + 1, pv - 1));
    if (pv + 1 <= r) s.insert(std::make_pair(pv + 1, r));
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]), p[--a[i]] = i;

    all.build(n, a);
    for (int i = 0; i < n; ++i) b[i] = (i & 1) ? MAXN : a[i];
    even.build(n, b);
    for (int i = 0; i < n; ++i) b[i] = (i & 1) ? a[i] : MAXN;
    odd.build(n, b);

    s.insert(std::make_pair(0, n - 1));
    while (!s.empty()) {
        auto r = *s.begin(); s.erase(s.begin());
        solve(r.first, r.second);
    }

    for (int i = 0; i < n; ++i) printf("%d%c", b[i] + 1, i == n - 1 ? '\n' : ' ');
    return 0;
}

Submission Info

Compile Error

g++: internal compiler error: Killed (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-5/README.Bugs> for instructions.