Submission #1866019

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
#define PI 3.14159265358979323846
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

const int MAXN = 262144;
const int oo = 1E9;

int n, in[MAXN], rpos[MAXN];
pii tree[2 * MAXN];  // even, odd

void Init(){
  for(int i = 0;i < n;++i){
    tree[MAXN + i] = mp(oo, oo);
    if(i & 1) tree[MAXN + i].se = in[i];
    else tree[MAXN + i].fi = in[i];
  }
  for(int i = MAXN - 1;i > 0;--i){
    tree[i].fi = min(tree[2 * i].fi, tree[2 * i + 1].fi);
    tree[i].se = min(tree[2 * i].se, tree[2 * i + 1].se);
  }
}

pii Get(int l, int r){
  l += MAXN, r += MAXN;

  pii res = tree[l];
  relaxMin(res.fi, tree[r].fi);
  relaxMin(res.se, tree[r].se);

  while(l != r){
    int pl = l >> 1, pr = r >> 1;
    if(pl == pr) break;
    relaxMin(res.fi, tree[l + 1].fi);
    relaxMin(res.se, tree[l + 1].se);
    relaxMin(res.fi, tree[r - 1].fi);
    relaxMin(res.se, tree[r - 1].se);
    l = pl, r = pr;
  }

  return res;
}

pii Solve(const pii& u){
  int x, y;
  if(u.fi & 1){
    x = Get(u.fi, u.se).se;
    y = Get(rpos[x] + 1, u.se).fi;
  } else {
    x = Get(u.fi, u.se).fi;
    y = Get(rpos[x] + 1, u.se).se;
  }
  return {x, y};
}

int main(){
  scanf("%d", &n);
  for(int i = 0;i < n;++i){
    scanf("%d", &in[i]);
    rpos[in[i]] = i;
  }

  Init();

  set<pair<pii, pii>> ival;
  ival.insert(mp(Solve(mp(0, n - 1)), mp(0, n - 1)));

  vi res;
  while(!ival.empty()){
    auto cur = *ival.begin();
    ival.erase(cur);

    //cout << cur.fi.fi << " : " << cur.fi.se << " | ";
    //cout << cur.se.fi << " : " << cur.se.se << endl;
    //system("pause");

    res.pb(cur.fi.fi);
    res.pb(cur.fi.se);

    int x = cur.fi.fi;
    int y = cur.fi.se;
    int px = rpos[x];
    int py = rpos[y];

    if(cur.se.fi < px){
      int a = cur.se.fi, b = px - 1;
      ival.insert(mp(Solve(mp(a, b)), mp(a, b)));
    }

    if(px + 1 <= py - 1){
      int a = px + 1, b = py - 1;
      ival.insert(mp(Solve(mp(a, b)), mp(a, b)));
    }

    if(py < cur.se.se){
      int a = py + 1, b = cur.se.se;
      ival.insert(mp(Solve(mp(a, b)), mp(a, b)));
    }
  }

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

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:71:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &in[i]);
                        ^

Judge Result