Filled with optimism, Hyunuk will host a conference about how great this new year will be!
The conference will have $n$ lectures. Hyunuk has two candidate venues $a$ and $b$. For each of the $n$ lectures, the speaker specified two time intervals $[sa_i, ea_i]$ ($sa_i \le ea_i$) and $[sb_i, eb_i]$ ($sb_i \le eb_i$). If the conference is situated in venue $a$, the lecture will be held from $sa_i$ to $ea_i$, and if the conference is situated in venue $b$, the lecture will be held from $sb_i$ to $eb_i$. Hyunuk will choose one of these venues and all lectures will be held at that venue.
Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval $[x, y]$ overlaps with a lecture held in interval $[u, v]$ if and only if $\max(x, u) \le \min(y, v)$.
We say that a participant can attend a subset $s$ of the lectures if the lectures in $s$ do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue $a$ or venue $b$ to hold the conference.
A subset of lectures $s$ is said to be venue-sensitive if, for one of the venues, the participant can attend $s$, but for the other venue, the participant cannot attend $s$.
A venue-sensitive set is problematic for a participant who is interested in attending the lectures in $s$ because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.Input
The first line contains an integer $n$ ($1 \le n \le 100\,000$), the number of lectures held in the conference.
Each of the next $n$ lines contains four integers $sa_i$, $ea_i$, $sb_i$, $eb_i$ ($1 \le sa_i, ea_i, sb_i, eb_i \le 10^9$, $sa_i \le ea_i, sb_i \le eb_i$).Output
Print “YES” if Hyunuk will be happy. Print “NO” otherwise.
You can print each letter in any case (upper or lower).Examplesinput
2 1 2 3 6 3 4 7 8
output
YES
input
3 1 3 2 4 4 5 6 7 3 4 5 5
output
NO
input
6 1 5 2 9 2 4 5 8 3 6 7 11 7 10 12 16 8 11 13 17 9 12 14 18
output
YES
Note
In second example, lecture set $\{1, 3\}$ is venue-sensitive. Because participant can’t attend this lectures in venue $a$, but can attend in venue $b$.
In first and third example, venue-sensitive set does not exist.
Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
int add = 0;
int sum = 0;
void apply(int l, int r, int v) {
add += v;
sum += (r - l + 1) * v;
}
};
node unite(const node &a, const node &b) const {
node res;
res.sum = a.sum + b.sum;
return res;
}
inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
if (tree[x].add != 0) {
tree[x + 1].apply(l, y, tree[x].add);
tree[z].apply(y + 1, r, tree[x].add);
tree[x].add = 0;
}
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v);
build(z, y + 1, r, v);
pull(x, z);
}
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[x + 1])) {
res = find_first_knowingly(x + 1, l, y, f);
} else {
res = find_first_knowingly(z, y + 1, r, f);
}
pull(x, z);
return res;
}
int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_first_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (ll <= y) {
res = find_first(x + 1, l, y, ll, rr, f);
}
if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}
int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[z])) {
res = find_last_knowingly(z, y + 1, r, f);
} else {
res = find_last_knowingly(x + 1, l, y, f);
}
pull(x, z);
return res;
}
int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_last_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
res = find_last(x + 1, l, y, ll, rr, f);
}
pull(x, z);
return res;
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
// find_first and find_last call all FALSE elements
// to the left (right) of the sought position exactly once
int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_first(0, 0, n - 1, ll, rr, f);
}
int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_last(0, 0, n - 1, ll, rr, f);
}
};
void Compress(vector<int>& a, vector<int>& b) {
vector<pair<int, int>> e;
for (int i = 0; i < (int) a.size(); i++) {
e.emplace_back(a[i], i);
}
for (int i = 0; i < (int) b.size(); i++) {
e.emplace_back(b[i], ~i);
}
sort(e.begin(), e.end());
int t = 0;
for (int i = 0; i < (int) e.size(); i++) {
if (i > 0 && e[i].first != e[i - 1].first) {
++t;
}
if (e[i].second >= 0) {
a[e[i].second] = t;
} else {
b[~e[i].second] = t;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> sa(n), ea(n), sb(n), eb(n);
for (int i = 0; i < n; i++) {
cin >> sa[i] >> ea[i] >> sb[i] >> eb[i];
}
Compress(sa, ea);
Compress(sb, eb);
debug(sa, ea, sb, eb);
for (int rot = 0; rot < 2; rot++) {
for (int flip = 0; flip < 2; flip++) {
segtree st(2 * n);
vector<pair<int, int>> events;
for (int i = 0; i < n; i++) {
events.emplace_back(sa[i], ~i);
events.emplace_back(ea[i], i);
}
sort(events.begin(), events.end());
for (auto& e : events) {
int id = e.second;
if (id < 0) {
id = ~id;
if (st.get(sb[id], eb[id]).sum > 0) {
cout << "NO" << '\n';
return 0;
}
} else {
st.modify(sb[id], eb[id], 1);
}
}
for (int i = 0; i < n; i++) {
sa[i] = 2 * n - 1 - sa[i];
ea[i] = 2 * n - 1 - ea[i];
swap(sa[i], ea[i]);
}
}
for (int i = 0; i < n; i++) {
swap(sa[i], sb[i]);
swap(ea[i], eb[i]);
}
}
cout << "YES" << "\n";
return 0;
}
