Submission #1489482

---

Source Code Expand

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

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

struct quq {
    int first, second;
    quq(int f = 0, int s = 0) : first(f), second(s) { }
    inline bool operator < (const quq &other) const {
        return (this->first == other.first) ?
            (this->second < other.second) : (this->first < other.first);
    }
};

struct rmq {
    quq f[LOGN][MAXN];
    inline void build(int n, int *a) {
        for (int i = 0; i < n; ++i) f[0][i] = quq(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 quq 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(u.second, 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

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:62:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; ++i) scanf("%d", &a[i]), p[--a[i]] = i;
                                                                  ^

Judge Result