Submission #8537172

---

Source Code Expand

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

typedef pair<int, int> pii;
const int N = int(2e5) + 7;
const int inf = int(1e9) + 7;

pii operator + (const pii& x, const pii& y) {
    if(x.fi < y.fi) return x;
    if(x.fi == y.fi && x.se > y.se) return x;
    return y;
}

struct TSegment {
    vector<int> l, h;
    vector<pii> st;
    int n;
    TSegment() {}
    void Init(int _n) {
        n = _n;
        l.resize(n << 2 | 1), h.resize(n << 2 | 1), st.resize(n << 2 | 1, mp(inf, inf));
        Build(1, 1, n);
    }
    void Build(int x, int low, int high) {
        l[x] = low, h[x] = high;
        if(l[x] == h[x]) return;
        int mid = (low + high) >> 1;
        Build(x << 1, low, mid);
        Build(x << 1 | 1, mid + 1, high);
    }
    void Update(int x, int pos, int val) {
        if(l[x] > pos || h[x] < pos) return;
        if(l[x] == h[x] && l[x] == pos) {
            st[x] = mp(val, pos); return;
        }
        Update(x << 1, pos, val);
        Update(x << 1 | 1, pos, val);
        st[x] = st[x << 1] + st[x << 1 | 1];
    }
    pii Find(int x, int low, int high) {
        if(l[x] > high || h[x] < low) return mp(inf, inf);
        if(l[x] >= low && h[x] <= high) return st[x];
        return Find(x << 1, low, high) + Find(x << 1 | 1, low, high);
    }
} it[2];

int n, cnt, p[N];
struct TNode {
    int x, y, px, py, l, r;
    TNode() {}
    TNode(int x, int y, int px, int py, int l, int r): x(x), y(y), px(px), py(py), l(l), r(r) {}
    bool operator<(const TNode& o)const& {return x > o.x;}
};
priority_queue<TNode> pq;
typedef pair<pii, pii> ii;

ii Get(int l, int r) {
    pii x = it[l & 1].Find(1, l, (r & 1) == (l & 1)? r - 2: r - 1);
    pii y = it[!(l & 1)].Find(1, x.se, r);
    return mp(x, y);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n; it[0].Init(n), it[1].Init(n);
    for(int i = 1; i <= n; ++i) {
        cin >> p[i];
        it[i & 1].Update(1, i, p[i]);
    }
    ii top = Get(1, n);
    pq.push(TNode(top.fi.fi, top.se.fi, top.fi.se, top.se.se, 1, n));
    while(pq.size()) {
        TNode cur = pq.top(); pq.pop();
        cout << cur.x << ' ' << cur.y << ' ';
        ///chia day (l, px - 1) (px + 1, py - 1) (py + 1, r)
        if(cur.px - 1 > cur.l) {
            top = Get(cur.l, cur.px - 1);
            pq.push(TNode(top.fi.fi, top.se.fi, top.fi.se, top.se.se, cur.l, cur.px - 1));
        }
        if(cur.px + 1 < cur.py - 1) {
            top = Get(cur.px + 1, cur.py - 1);
            pq.push(TNode(top.fi.fi, top.se.fi, top.fi.se, top.se.se, cur.px + 1, cur.py - 1));
        }
        if(cur.py + 1 < cur.r) {
            top = Get(cur.py + 1, cur.r);
            pq.push(TNode(top.fi.fi, top.se.fi, top.fi.se, top.se.se, cur.py + 1, cur.r));
        }
    }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int32_t main()’:
./Main.cpp:74:40: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
                                        ^
./Main.cpp:75:41: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
                                         ^

Judge Result