Submission #1866973

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll sparse_odd[222222][20], sparse_even[222222][20], idx[222222], a[222222];

bool cmp(ii a, ii b){
	ll x = INF;
	ll y = INF;
	ll l = a.fi;
	ll r = a.se;
	if(l%2==0){
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				x=min(x,sparse_even[l][i]);
				l+=(1<<i);
			}
		}
	}
	else{
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				x=min(x,sparse_odd[l][i]);
				l+=(1<<i);
			}
		}
	}
	l = b.fi;
	r = b.se;
	if(l%2==0){
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				y=min(y,sparse_even[l][i]);
				l+=(1<<i);
			}
		}
	}
	else{
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				y=min(y,sparse_odd[l][i]);
				l+=(1<<i);
			}
		}
	}
	return x>y;
}

priority_queue <ii, vii, function<bool(ii,ii)> > solve(cmp);
vector<ii> ans;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		idx[a[i]]=i;
		if(i%2){
			sparse_odd[i][0]=a[i];
			sparse_even[i][0]=INF;
		}
		else{
			sparse_odd[i][0]=INF;
			sparse_even[i][0]=a[i];
		}
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i < n; i++){
			if(i+(1<<j)-1<n){
				sparse_even[i][j]=min(sparse_even[i][j-1],sparse_even[i+(1<<(j-1))][j-1]);
				sparse_odd[i][j]=min(sparse_odd[i][j-1],sparse_odd[i+(1<<(j-1))][j-1]);
			}
		}
	}
	solve.push(mp(0,n));
	while(!solve.empty()){
		ll l, r, l1;
		ll x=INF;
		l = solve.top().fi;
		r = solve.top().se;
		solve.pop();
		if(l<r){
			if(l%2==0){
			l1=l;
			for(int i = 19; i >= 0; i--){
				if(l+(1<<i)-1<r){
					x=min(x,sparse_even[l][i]);
					l+=(1<<i);
				}
			}
			ll y=INF;
			l=idx[x]+1;
			for(int i = 19; i >= 0; i--){
				if(l+(1<<i)-1<r){
					y=min(y,sparse_odd[l][i]);
					l+=(1<<i);
				}
			}
			ans.pb(mp(x,y));
			solve.push(mp(l1,idx[x]));
			solve.push(mp(idx[x]+1,idx[y]));
			solve.push(mp(idx[y]+1,r));
			}
			else{
				l1=l;
				for(int i = 19; i >= 0; i--){
					if(l+(1<<i)-1<r){
						x=min(x,sparse_odd[l][i]);
						l+=(1<<i);
					}
				}
				ll y=INF;
				l=idx[x]+1;
				for(int i = 19; i >= 0; i--){
					if(l+(1<<i)-1<r){
						y=min(y,sparse_even[l][i]);
						l+=(1<<i);
					}
				}
				ans.pb(mp(x,y));
				solve.push(mp(l1,idx[x]));
				solve.push(mp(idx[x]+1,idx[y]));
				solve.push(mp(idx[y]+1,r));
			}
		}
	}
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i].fi << ' ' << ans[i].se << ' ';
	}
	return 0;
}

Submission Info

Judge Result