参照了快速排序的思想,每次随机中点并分治。
TLE 6 AC 25
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define ctz __builtin_ctz
#define gc getchar()
#define mkpr make_pair
#define i128 __int128
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
template <class T>
void write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x >= 10)
{
write(x / 10);
}
putchar(x % 10 ^ 48);
}
template <class T>
void read(T &x)
{
x = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= f;
}
template <class T>
T quick_pow(T a, T b, T p = -1)
{
if (p == -1)
{
T res = 1;
while (b)
{
if (b & 1)
res = res * a;
a *= a;
b >>= 1;
}
return res;
}
else
{
T res = 1;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
}
template <class T>
T inv(T x, T p) { return quick_pow(x, p - 2, p); }
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll invll(ll a, ll mod)
{
return qpow(a, mod - 2, mod);
}
struct Matrix
{
vector<vector<ll>> mp;
ll p;
int size;
// 第二个参数:是否设为单位矩阵
void init(int siz, ll mod = -1, bool isdw = 0)
{
p = mod;
size = siz;
mp.resize(siz);
for (int i = 0; i < siz; i++)
{
mp[i].resize(siz);
for (int j = 0; j < siz; j++)
{
mp[i][j] = 0;
}
if (isdw)
mp[i][i] = 1;
}
}
Matrix operator*(const Matrix &b)
{
Matrix res;
res.init(max(size, b.size), p);
for (int i = 0; i < size; i++)
{
for (int k = 0; k < size; k++)
{
for (int j = 0; j < size; j++)
{
if (k >= b.size || j >= b.size)
{
continue;
}
res.mp[i][j] += mp[i][k] * b.mp[k][j];
if (res.p != -1)
res.mp[i][j] %= res.p;
}
}
}
return res;
}
};
Matrix quick_pow_mat(Matrix a, ll b)
{
Matrix res;
res.init(a.size, a.p, 1);
while (b)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
mt19937 rnd(random_device{}());
template <const int mod>
class static_mint
{
public:
int mval = 0, minv = -1;
static_mint()
{
mval = 0;
minv = -1;
}
static_mint(int val)
{
this->mval = val % mod;
this->minv = -1;
}
int val()
{
return mval;
}
int inv()
{
if (minv != -1)
return minv;
else
return minv = qpow(mval, mod - 2, mod);
}
static_mint operator=(int b)
{
this->mval = b % mod;
this->minv = -1;
return *this;
}
operator int()
{
return int(mval);
}
operator ll()
{
return ll(mval);
}
operator double()
{
return (double)(mval);
}
operator float()
{
return (float)(mval);
}
bool operator!=(static_mint b)
{
return mval != b.val();
}
static_mint operator+(static_mint b)
{
return static_mint((1ll * mval + b.val()) % (ll)mod);
}
static_mint operator-(static_mint b)
{
int res = (1ll * mval - b.val()) % (ll)mod + mod;
if (res >= mod)
res -= mod;
return static_mint(res);
}
static_mint operator*(static_mint b)
{
int res = 1ll * mval * b.val() % (ll)mod;
return static_mint(res);
}
static_mint operator/(static_mint b)
{
int res = 1ll * mval * b.inv() % (ll)mod;
return static_mint(res);
}
static_mint operator+=(static_mint b)
{
mval = (1ll * mval + b.val()) % (ll)mod;
minv = -1;
return *this;
}
static_mint operator-=(static_mint b)
{
mval = (1ll * mval - b.val()) % (ll)mod + mod;
if (mval >= mod)
mval -= mod;
minv = -1;
return *this;
}
static_mint operator*=(static_mint b)
{
mval = 1ll * mval * b.val() % (ll)mod;
minv = -1;
return *this;
}
static_mint operator/=(static_mint b)
{
mval = 1ll * mval * b.inv() % (ll)mod;
minv = -1;
return *this;
}
// ===========================
// b's type = int
static_mint operator+(int b)
{
return static_mint((1ll * mval + b) % (ll)mod);
}
static_mint operator-(int b)
{
int res = (1ll * mval - b) % (ll)mod + mod;
if (res >= mod)
res -= mod;
return static_mint(res);
}
static_mint operator*(int b)
{
int res = 1ll * mval * b % (ll)mod;
return static_mint(res);
}
static_mint operator/(int b)
{
int res = 1ll * mval * invll(b, mod) % (ll)mod;
return static_mint(res);
}
static_mint operator+=(int b)
{
mval = (1ll * mval + b) % (ll)mod;
minv = -1;
return *this;
}
static_mint operator-=(int b)
{
mval = (1ll * mval - b) % (ll)mod + mod;
if (mval >= mod)
mval -= mod;
minv = -1;
return *this;
}
static_mint operator*=(int b)
{
mval = 1ll * mval * b % (ll)mod;
minv = -1;
return *this;
}
static_mint operator/=(int b)
{
mval = 1ll * mval * invll(b, mod) % (ll)mod;
minv = -1;
return *this;
}
bool operator!=(int b)
{
return mval != b;
}
};
const int maxn = 2e5 + 5;
struct Edge
{
int a, b;
} edge[maxn];
int n;
deque<Edge> lef, rig;
bool QuickSort(int l, int r)
{
if (r - l + 1 <= 1)
return 0;
int mid = l+rnd()%(r-l+1);
int midl = edge[mid].a, midr = edge[mid].b;
if (midl > midr)
swap(midl, midr);
auto temp = edge[mid];
FOR(i, l, r)
{
if (i == mid)
continue;
if (edge[i].a >= midl && edge[i].a <= midr)
{
if (!(edge[i].b >= midl && edge[i].b <= midr))
{
puts("Yes");
exit(0);
// printf("1 %d %d pd = %d\n",l,r,i);
return 1;
}
else
{
lef.push_back(edge[i]);
}
}
else
{
if ((edge[i].b >= midl && edge[i].b <= midr))
{
puts("Yes");
exit(0);
// printf("2 %d %d pd = (%d,%d) mid = (%d,%d)\n",l,r,edge[i].a,edge[i].b,edge[mid].a,edge[mid].b);
return 1;
}
else
{
rig.push_back(edge[i]);
}
}
}
int point = l;
while (!lef.empty())
{
edge[point++] = lef.front();
lef.pop_front();
}
int midp = point;
edge[point++] = temp;
while (!rig.empty())
{
edge[point++] = rig.front();
rig.pop_front();
}
if (rnd() & 1)
{
if (QuickSort(midp + 1, r))
{
puts("Yes");
exit(0);
}
if (QuickSort(l, midp - 1))
{
puts("Yes");
exit(0);
}
}
else
{
if (QuickSort(l, midp - 1))
{
puts("Yes");
exit(0);
}
if (QuickSort(midp + 1, r))
{
puts("Yes");
exit(0);
}
}
return 0;
}
int main()
{
scanf("%d", &n);
FOR(i, 1, n)
{
scanf("%d%d", &edge[i].a, &edge[i].b);
}
random_shuffle(edge+1,edge+n+1);
puts(QuickSort(1, n) ? "Yes" : "No");
return 0;
}