Submission #1500502

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define fi first
#define se second
#define INF 100000000
using namespace std;
typedef pair<int, int> pii;

int N, A[200000];

class SegmentTree {
  int n;
  vector<pii> dat;

public:
  SegmentTree(int size) {
    n = 1;
    while(n < size) n *= 2;
    REP(i, 0, 2 * n - 1) dat.push_back(pii(INF, INF));
  }

  pii query(int a, int b) { return rquery(a, b, 0, 0, n); }

  void update(int k, pii a) {
    k += n - 1;
    dat[k] = a;
    while(k > 0) {
      k = (k - 1) / 2;
      dat[k] = op(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }

private:
  pii rquery(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return pii(INF, INF);
    if(a <= l && r <= b) return dat[k];
    pii vl = rquery(a, b, k * 2 + 1, l, (l + r) / 2);
    pii vr = rquery(a, b, k * 2 + 2, (l + r) / 2, r);
    return op(vl, vr);
  }

  pii op(pii a, pii b) { return min(a, b); }
};

struct segment {
  int l, r;
  pii v;

public:
  bool operator<(const segment &s) const { return v > s.v; }
};

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> A[i];

  SegmentTree eve(N / 2), odd(N / 2);
  REP(i, 0, N / 2) {
    eve.update(i, pii(A[i * 2 + 0], i * 2 + 0));
    odd.update(i, pii(A[i * 2 + 1], i * 2 + 1));
  }

  priority_queue<segment> q;
  q.push((segment) { 0, N, eve.query(0, N / 2) });
  vector<int> ans;
  while(q.size()) {
    struct segment s = q.top();
    q.pop();

    if(s.l >= s.r) continue;

    pii t = (s.l % 2 == 0 ? odd : eve).query((s.v.se + 1) / 2, (s.r + 1) / 2);
    ans.push_back(s.v.fi);
    ans.push_back(t.fi);
    q.push((segment) { s.l,        s.v.se, (s.l          % 2 == 0 ? eve : odd).query(s.l / 2,          s.v.se / 2) });
    q.push((segment) { s.v.se + 1, t.se,   ((s.v.se + 1) % 2 == 0 ? eve : odd).query((s.v.se + 1) / 2, t.se / 2) });
    q.push((segment) { t.se + 1,   s.r,    ((t.se + 1)   % 2 == 0 ? eve : odd).query((t.se + 1) / 2,   s.r / 2) });
  }

  REP(i, 0, ans.size()) cout << ans[i] << (i + 1 != N ? " " : "\n");
}

Submission Info

Judge Result