Submission #1691862

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=2e5+5,inf=1e9+10;
int n;
int tag[maxn<<2],mini[maxn<<2][2];
int pos[maxn];
set<int>used;
void U(int x){
	rep(i,0,1)mini[x][i]=min(mini[ls][i],mini[rs][i]);
}
void B(int x,int l,int r){
	mini[x][0]=mini[x][1]=inf;
	if(l==r){
		read(mini[x][l&1]);
		pos[mini[x][l&1]]=l;
		return;
	}
	B(ls,l,mid);B(rs,mid+1,r);
	U(x);
}
void R(int x){
	tag[x]^=1;
	swap(mini[x][0],mini[x][1]);
}
void PD(int x){
	if(!tag[x])return;
	R(ls);R(rs);tag[x]^=1;
}
void R(int x,int l,int r,int ll,int rr){
	if(ll>rr)return;
	if(l==ll&&r==rr){
		R(x);
		return;
	}
	PD(x);
	if(rr<=mid)R(ls,l,mid,ll,rr);
	else if(ll>mid)R(rs,mid+1,r,ll,rr);
	else R(ls,l,mid,ll,mid),R(rs,mid+1,r,mid+1,rr);
	U(x);
}
void M(int x,int l,int r,int pos){
	if(l==r){
		mini[x][0]=mini[x][1]=inf;
		return;
	}
	PD(x);
	if(pos<=mid)M(ls,l,mid,pos);
	else M(rs,mid+1,r,pos);
	U(x);
}
int Q(int x,int l,int r,int ll,int rr,int i){
	if(l==ll&&r==rr)return mini[x][i];
	PD(x);
	if(rr<=mid)return Q(ls,l,mid,ll,rr,i);
	else if(ll>mid)return Q(rs,mid+1,r,ll,rr,i);
	else return min(Q(ls,l,mid,ll,mid,i),Q(rs,mid+1,r,mid+1,rr,i));
}
int main(){
	read(n);
	B(1,1,n);
	used.insert(n+1);
	rep(i,1,n/2){
		int minv=Q(1,1,n,1,n,1),now=pos[minv];
		int r=*used.lower_bound(now)-1;
		int secv=Q(1,1,n,now+1,r,0),nxt=pos[secv];
		R(1,1,n,now+1,nxt-1);
		M(1,1,n,now);
		M(1,1,n,nxt);
		printf("%d %d ",minv,secv);
		used.insert(now);
		used.insert(nxt);
	}
	return 0;
}

Submission Info

Judge Result