1348F - Phoenix and Memory - CodeForces Solution

#include <cstdio>
#include <utility>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#define debug(...) fprintf(stderr, __VA_ARGS__)

inline int rd() {
	int x = 0, f = 1, c = getchar();
	while (((c - '0') | ('9' - c)) < 0)
		f = c != '-', c = getchar();
	while (((c - '0') | ('9' - c)) > 0)
		x = x * 10 + c - '0', c = getchar();
	return f ? x : -x;
}

using pii = std::pair<int, int>;

const int N = 2e5;

int n;
pii a[N + 5]; int pos[N + 5];
int p[N + 5];

#define lch (p * 2)
#define rch (p * 2 + 1)
#define mid ((cl + cr) / 2)
struct node {
	int c, tg;
	void upd(int v) {
		c = tg = v;
	}
} t[N * 4 + 5];
void pushdown(int p) {
	if(!t[p].tg) return;
	t[lch].upd(t[p].tg), t[rch].upd(t[p].tg);
	t[p].tg = 0;
}
void upd(int l, int r, int v, int p = 1, int cl = 1, int cr = n) {
	if(cl == l && cr == r) return t[p].upd(v);
	pushdown(p);
	if(r <= mid) upd(l, r, v, lch, cl, mid);
	else if(l > mid) upd(l, r, v, rch, mid + 1, cr);
	else upd(l, mid, v, lch, cl, mid), upd(mid + 1, r, v, rch, mid + 1, cr);
}
int que(int x, int p = 1, int cl = 1, int cr = n) {
	if(cl == cr) return t[p].c;
	pushdown(p);
	return (x <= mid) ? que(x, lch, cl, mid) : que(x, rch, mid + 1, cr);
}
#undef lch
#undef rch
#undef mid

struct Q { int x, flg, id; }; std::vector<Q> q[N + 5]; int ans[N + 5], pre[N + 5];

int main() {
	n = rd();
	for(int i = 1; i <= n; i++) a[i] = {rd(), rd()}, pos[i] = i;
	std::sort(pos + 1, pos + 1 + n, [](int i, int j) { return a[i] < a[j]; });

//	for(int i = 1; i <= n; i++) {
//		debug("%d: %d, %d\n", i, a[pos[i]].first, a[pos[i]].second);
//	}

	std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
	for(int i = 1, j = 1; i <= n; i++) {
		while(j <= n && a[pos[j]].first == i) {
			pq.push({a[pos[j]].second, pos[j]});
			j++;
		}
		p[pq.top().second] = i; pq.pop();
	}

	for(int i = 1; i <= n; i++) pos[i] = i;
	std::sort(pos + 1, pos + 1 + n, [](int i, int j) { return p[i] < p[j]; });
	for(int i = 1; i <= n; i++) {
		auto [l, r] = a[i];
		q[l - 1].push_back({p[i], -1, i});
		q[r].push_back({p[i], 1, i});
	}
	for(int i = 1; i <= n; i++) {
		upd(a[pos[i]].first, a[pos[i]].second, pos[i]);
		for(auto [x, flg, id] : q[i]) {
			int c = que(x);
			if(flg == 1) { if(c != pre[id]) ans[id] = c; }
			else pre[id] = c;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(ans[i] && ans[i] != i) {
			puts("NO");
			for(int j = 1; j <= n; j++) printf("%d%c", p[j], " \n"[j == n]);
			std::swap(p[i], p[ans[i]]);
			for(int j = 1; j <= n; j++) printf("%d%c", p[j], " \n"[j == n]);
			return 0;
		}
	}
	puts("YES");
	for(int i = 1; i <= n; i++) printf("%d%c", p[i], " \n"[i == n]);
	return 0;
}

/*
8
3 3
3 5
2 3
1 1
5 7
7 7
5 5
3 8
*/