提出 #45903621

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2e5+10,INF = 1e9;

int n,a[MAXN*2],L[MAXN],R[MAXN],arr[MAXN],p[MAXN],pre[MAXN];

int X[MAXN],Y[MAXN],rk[MAXN];

#define mid ((l+r)>>1)
struct Seg{ //单点删除，求所有Xi = premin X里Yi的最小值
	int mn[MAXN<<2],t[MAXN<<2];
	int calc(int x,int l,int r,int pre){
		if(l==r)return (pre > mn[x]) ? (Y[l]) : (INF); 
		
		if(pre > mn[lc(x)])return min(calc(lc(x),l,mid,pre),t[x]);
		else return calc(rc(x),mid+1,r,pre);
	}
	void pu(int x,int l,int r){
		mn[x] = min(mn[lc(x)],mn[rc(x)]);
		t[x] = calc(rc(x),mid+1,r,mn[lc(x)]);
	}
	void build(int x,int l,int r){
		if(l==r){
			mn[x] = X[l];
			return;
		}
		build(lc(x),l,mid);build(rc(x),mid+1,r);
		pu(x,l,r);
	}
	void mdf(int x,int l,int r,int pos){
		if(l==r)return (void)(mn[x] = INF);
		(pos<=mid)?(mdf(lc(x),l,mid,pos)) : (mdf(rc(x),mid+1,r,pos));
		pu(x,l,r);
	}
}seg;
#undef mid

int main(){
	ios::sync_with_stdio(false);

	cin>>n;
	rep(i,1,2*n)cin>>a[i],arr[i] = i;

	rep(i,1,2*n)R[a[i]] = i;
	per(i,2*n,1)L[a[i]] = i;

	sort(arr+1,arr+1+n,[&](int x,int y){return R[x] < R[y];});

	rep(i,1,n)X[i] = L[arr[i]],Y[i] = arr[i],rk[Y[i]] = i;

	seg.build(1,1,n);

	rep(i,1,n){
		int val = seg.calc(1,1,n,INF);
		assert(val != INF);

		p[i] = val;
		seg.mdf(1,1,n,rk[val]);
	}

	rep(i,1,n)cout<<p[i]<<" "<<p[i]<<" ";

    return 0;
}

提出情報

ジャッジ結果