Submission #2092619

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define inf 1000000000

using namespace std;
typedef pair<int, int> P;

struct SegTree{
	int size;
	vector<P> seg;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
	}
	
	void init(){
		for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(inf, inf);
	}
	
	void update(int i, P val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = min(seg[i*2], seg[i*2+1]);
		}
	}

	P query(int a, int b, int k, int l, int r)
	{
		if(b < l || r < a) return make_pair(inf, inf);
		if(a <= l && r <= b) return seg[k];
		P lval = query(a, b, k*2, l, (l+r)/2);
		P rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return min(lval, rval);
	}
	P query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

SegTree odd(18), even(18);

struct Range{
	int l, r;
	P p1, p2;
	
	Range(){}
	Range(int a, int b){
		l = a, r = b;
		calc();
	}
	void calc(){
		if(l%2){
			p1 = odd.query(l, r);
			p2 = even.query(p1.second+1, r);
		}
		else{
			p1 = even.query(l, r);
			p2 = odd.query(p1.second+1, r);
		}
	}
	bool operator>(const Range& obj)const{
		return p1 > obj.p1;
	}
};

int N;
priority_queue< Range, vector<Range>, greater<Range> > Q;
vector<int> ans;

int main(void)
{
	odd.init(), even.init();
	
	cin >> N;
	int p;
	for(int i = 1; i <= N; i++){
		cin >> p;
		if(i%2) odd.update(i, make_pair(p, i));
		else even.update(i, make_pair(p, i));
	}
	
	Range rg;
	Q.push(Range(1, N));
	while(Q.size()){
		rg = Q.top(), Q.pop();
		ans.push_back(rg.p1.first);
		ans.push_back(rg.p2.first);
		if(rg.p1.second != rg.l) Q.push(Range(rg.l, rg.p1.second-1));
		if(rg.p2.second != rg.r) Q.push(Range(rg.p2.second+1, rg.r));
		if(rg.p1.second+1 != rg.p2.second) Q.push(Range(rg.p1.second+1, rg.p2.second-1));
	}
	
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i];
		if(i != ans.size()-1) cout << " ";
	}
	cout << endl;
	
	return 0;
}

Submission Info

Judge Result