Submission #1488151

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct segtree{
  in MX;
  const in inf=10000000000LL;
  vector<pair<in,in> > mxp;
  VI lft,rgt;
  pair<in,in> comb(pair<in,in> a, pair<in,in> b){
    if(a.first<b.first)
      return a;
    return b;
  }
  pair<in,in> mnin(in l, in r, in id=1){
    if(r<lft[id] || l>rgt[id])return MP(inf,0);
    if(l<=lft[id] && r>=rgt[id])return mxp[id];
    return comb(mnin(l,r,2*id),mnin(l,r,2*id+1));
  }
  void ini(in n,VI hv){
    MX=1;
    while(MX<n)
      MX*=2;
    mxp.resize(2*MX);
    forv(i,mxp)
      mxp[i]=MP(inf,i-MX);
    forn(i,n)
      mxp[i+MX].first=hv[i];
    lft=rgt=VI(2*MX);
    forn(i,MX)
      lft[i+MX]=rgt[i+MX]=i;
    for(in i=MX-1;i>=1;--i){
      lft[i]=lft[2*i];
      rgt[i]=rgt[2*i+1];
      mxp[i]=comb(mxp[2*i],mxp[2*i+1]);
    }
  }
};
vector<pair<in,in> > res;
segtree par[2];
map<pair<in,in>,vector<pair<in,in> > > unlck;
priority_queue<pair<in,in> > q;
void genpairs(in l, in r, pair<in,in> pp){
  assert((r-l+1)%2==0);
  if(l>=r)
    return;
  pair<in,in> c=par[l%2].mnin(l,r);
  pair<in,in> d=par[(l+1)%2].mnin(c.second+1,r);
  unlck[pp].PB(MP(c.first,d.first));
  genpairs(l,c.second-1,MP(c.first,d.first));
  genpairs(c.second+1,d.second-1,MP(c.first,d.first));
  genpairs(d.second+1,r,MP(c.first,d.first));
}
void mkn(pair<in,in> u){
  vector<pair<in,in> >& v=unlck[u];
  forv(i,v)
    q.push(MP(-v[i].first,v[i].second));
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  VI p[2];
  in a;
  forn(z,n){
    cin>>a;
    p[z%2].PB(a);
    p[(z+1)%2].PB(1e9);
  }
  par[0].ini(n,p[0]);
  par[1].ini(n,p[1]);
  genpairs(0,n-1,MP(0,0));
  mkn(MP(0,0));
  forn(zz,n/2){
    pair<in,in> u=q.top();
    u.first=-u.first;
    q.pop();
    res.PB(u);
    mkn(u);
  }
  forv(i,res)
    cout<<res[i].first<<" "<<res[i].second<<" ";
  cout<<"\n";
  return 0;
}

Submission Info

Judge Result