提出 #45791936

---

ソースコード 拡げる

// LUOGU_RID: 125558222
#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 4e5 + 10;
int n, a[N], t[2][N];//, p[N];
bool vis[N];
// set <int> b;
// set <int> s;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
int seg[N << 2];
set <int> g;
void pushup(int num) {
	seg[num] = min(seg[ls], seg[rs]);
}
void modify(int num, int l, int r, int x, int y) {
	if (l == r) {
		seg[num] = y;
		return;
	}
	int mid = (l + r) >> 1;
	if (mid >= x) modify(li, x, y);
	else modify(ri, x, y);
	pushup(num);
}
int findpos(int num, int l, int r, int x, int y) {
	if (seg[num] >= y) return -1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (mid > x) {
		int t = findpos(li, x, y);
		if (~t) return t;
	}
	return findpos(ri, x, y);
}
int sub(int x) {
	int g = findpos(1, 1, 2 * n, x, t[1][a[x]]);
	// cout << x << " " << g << " " << a[x] << " " << t[1][a[x]] << endl;
	return g;
}
void add(int x) {
	g.insert(x);
	q.emplace(a[x], x);
}
void build() {
	// puts("!!!");
	// int x = *s.begin();
	// int l = 0, r = n + 1;
	int x = 0;
	while (true) {
		int y = sub(x);
		// cout << " -> " << x << " " << y << endl;
		if (y == -1) break;
		add(y);
		x = y;
		// auto it = s.lower_bound(x);
		// if (it == )
		// if (t[1][a[x]] == x + 1) break;
	}
}
signed main() {
	read(n);
	t[1][0] = 2 * n + 1;
	F(i, 1, n * 2) {
		read(a[i]);
		// cout << " -> " << !!t[0][a[i]] << endl;
		t[!!t[0][a[i]]][a[i]] = i;
		// s.insert(i);
	}
	g.insert(0);
	ms(seg, 0x3f);
	F(i, 1, n) modify(1, 1, 2 * n, t[0][i], t[1][i]);//, cout << "& " << t[0][i] << " " << t[1][i] << endl;
	F(i, 1, n) {
		if (q.empty()) build();
		int x = q.top().second; q.pop();
		// cout << "# " << x << endl;
		cout << a[x] << " " << a[x] << " ";
		// debug << x << " " << a[x] << endl;
		modify(1, 1, 2 * n, x, 1e9);
		// p[t[0][x]] = p[t[1][x]] = i;
		// cout << a[x] << " ";
		g.erase(x);
		int pos = *prev(g.lower_bound(x)), pp = sub(pos);
		// cout << " -> " << pos << " " << pp << endl;
		while (pp != -1 && !g.count(pp)) {
			add(pp);
			pp = sub(pp);
		}
	}
	// F(i, 1, 2 * n) cout << p[i] << " ";
	return 0;
}

提出情報

ジャッジ結果