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 100000$), 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).


-----Examples-----

Input
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.

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Sorting

Data structures


Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip()
N = int(input())
W = [(i + 1000007) ** 3 % 998244353 for i in range(N)]
(AL, AR, BL, BR) = ([], [], [], [])
for i in range(N):
	(a, b, c, d) = map(int, input().split())
	AL.append(a)
	AR.append(b)
	BL.append(c)
	BR.append(d)

def chk(L, R):
	D = {s: i for (i, s) in enumerate(sorted(list(set(L + R))))}
	X = [0] * 200200
	for (i, l) in enumerate(L):
		X[D[l]] += W[i]
	for i in range(1, 200200):
		X[i] += X[i - 1]
	return sum([X[D[r]] * W[i] for (i, r) in enumerate(R)])
print('YES' if chk(AL, AR) == chk(BL, BR) else 'NO')


import sys
input = lambda : sys.stdin.readline().rstrip()
N = 100101
n = int(input())
rand = [(i + 12345) ** 3 % 998244353 for i in range(N * 2 + 20)]
(al, ar, bl, br) = ([], [], [], [])
for _ in range(n):
	(a, b, c, d) = map(int, input().split())
	al.append(a)
	ar.append(b)
	bl.append(c)
	br.append(d)

def calk(l, r):
	ma = {s: idx for (idx, s) in enumerate(sorted(list(set(l + r))))}
	hash = [0] * N * 2
	for (idx, v) in enumerate(l):
		hash[ma[v]] += rand[idx]
	for i in range(1, N * 2):
		hash[i] += hash[i - 1]
	return sum([hash[ma[v]] * rand[idx] for (idx, v) in enumerate(r)])
print('YES' if calk(al, ar) == calk(bl, br) else 'NO')


import sys
input = sys.stdin.readline
import heapq
n = int(input())
C = [tuple(map(int, input().split())) for i in range(n)]
CA = []
CB = []
for (ind, (a, b, c, d)) in enumerate(C):
	CA.append((a, 0, ind))
	CA.append((b, 1, ind))
	CB.append((c, 0, ind))
	CB.append((d, 1, ind))
CA.sort()
CB.sort()
SMAX = []
EMIN = []
FINISHED = [0] * n
for (time, flag, ind) in CA:
	if flag == 0:
		heapq.heappush(SMAX, (-C[ind][2], ind))
		heapq.heappush(EMIN, (C[ind][3], ind))
		while FINISHED[SMAX[0][1]]:
			heapq.heappop(SMAX)
		while FINISHED[EMIN[0][1]]:
			heapq.heappop(EMIN)
		if -SMAX[0][0] > EMIN[0][0]:
			print('NO')
			sys.exit()
	else:
		FINISHED[ind] = 1
SMAX = []
EMIN = []
FINISHED = [0] * n
for (time, flag, ind) in CB:
	if flag == 0:
		heapq.heappush(SMAX, (-C[ind][0], ind))
		heapq.heappush(EMIN, (C[ind][1], ind))
		while FINISHED[SMAX[0][1]]:
			heapq.heappop(SMAX)
		while FINISHED[EMIN[0][1]]:
			heapq.heappop(EMIN)
		if -SMAX[0][0] > EMIN[0][0]:
			print('NO')
			sys.exit()
	else:
		FINISHED[ind] = 1
print('YES')


MOD = 10 ** 18 + 13
import sys
readline = sys.stdin.readline
from random import randrange

def compress(L):
	L2 = list(set(L))
	L2.sort()
	C = {v: k for (k, v) in enumerate(L2, 1)}
	return (L2, C)
N = int(readline())
T = set()
L = [None] * N
for i in range(N):
	L[i] = tuple(map(int, readline().split()))
	T |= set(L[i])
(t2, C) = compress(list(T))
Z = len(t2)
L = [[j] + [C[L[j][i]] for i in range(4)] for j in range(N)]
seed = []
while len(set(seed)) != N:
	seed = [randrange(1, MOD) for _ in range(N)]
S1 = [0] * (Z + 2)
S2 = [0] * (Z + 2)
S3 = [0] * (Z + 2)
S4 = [0] * (Z + 2)
p1 = [0] * N
p2 = [0] * N
for i in range(N):
	(j, s1, t1, s2, t2) = L[i]
	S1[s1] += seed[j]
	S2[t1] += seed[j]
	S3[s2] += seed[j]
	S4[t2] += seed[j]
for i in range(1, Z + 1):
	S1[i] = (S1[i] + S1[i - 1]) % MOD
	S2[i] = (S2[i] + S2[i - 1]) % MOD
	S3[i] = (S3[i] + S3[i - 1]) % MOD
	S4[i] = (S4[i] + S4[i - 1]) % MOD
for i in range(N):
	(j, s1, t1, s2, t2) = L[i]
	p1[j] = (S2[s1 - 1] - S1[t1]) % MOD
	p2[j] = (S4[s2 - 1] - S3[t2]) % MOD
print('YES' if all((a == b for (a, b) in zip(p1, p2))) else 'NO')


from operator import itemgetter
import sys
import bisect
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit0 = [0] * (n + 1)
		self.bit1 = [0] * (n + 1)

	def _add(self, bit, i, val):
		i = i + 1
		while i <= self.n:
			bit[i] += val
			i += i & -i

	def _get(self, bit, i):
		s = 0
		while i > 0:
			s += bit[i]
			i -= i & -i
		return s

	def add(self, l, r, val):
		self._add(self.bit0, l, -val * l)
		self._add(self.bit0, r, val * r)
		self._add(self.bit1, l, val)
		self._add(self.bit1, r, -val)

	def get_sum(self, l, r):
		return self._get(self.bit0, r) + r * self._get(self.bit1, r) - self._get(self.bit0, l) - l * self._get(self.bit1, l)

def compress(array):
	n = len(array)
	m = len(array[0])
	set_ = set()
	for i in array:
		for j in i:
			set_.add(j)
	array2 = sorted(set_)
	memo = {value: index for (index, value) in enumerate(array2)}
	for i in range(n):
		for j in range(m):
			array[i][j] = memo[array[i][j]]
	return (array, len(memo))
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
(info, m) = compress(info)
info = sorted(info, key=itemgetter(0))
bi = [None] * n
for i in range(n):
	bi[i] = (i, info[i][1])
bi = sorted(bi, key=itemgetter(1))
bii = [v for (i, v) in bi]
bit = BIT(m)
tmp = 0
for i in range(n):
	(l, r, l2, r2) = info[i]
	ind = bisect.bisect_left(bii, l)
	while tmp < ind:
		ii = bi[tmp][0]
		bit.add(info[ii][2], info[ii][3] + 1, 1)
		tmp += 1
	if bit.get_sum(l2, r2 + 1) >= 1:
		print('NO')
		exit()
for i in range(n):
	(info[i][0], info[i][1], info[i][2], info[i][3]) = (info[i][2], info[i][3], info[i][0], info[i][1])
info = sorted(info, key=itemgetter(0))
bi = [None] * n
for i in range(n):
	bi[i] = (i, info[i][1])
bi = sorted(bi, key=itemgetter(1))
bii = [v for (i, v) in bi]
bit = BIT(m)
tmp = 0
for i in range(n):
	(l, r, l2, r2) = info[i]
	ind = bisect.bisect_left(bii, l)
	while tmp < ind:
		ii = bi[tmp][0]
		bit.add(info[ii][2], info[ii][3] + 1, 1)
		tmp += 1
	if bit.get_sum(l2, r2 + 1) >= 1:
		print('NO')
		exit()
print('YES')


import sys
input = lambda : sys.stdin.readline().rstrip()
import time
a = time.time()
ke = int(a * 2 ** 20) % 2 ** 20 + 2 ** 20
pp = 100001000000000000021

def rand():
	global ke
	ke = ke ** 2 % pp
	return (ke >> 30) % (1 << 15) + (1 << 15)
N = int(input())
W = [rand() for _ in range(N)]
A = []
B = []
for i in range(N):
	(a, b, c, d) = map(int, input().split())
	A.append((a + 1, b + 2, i))
	B.append((c + 1, d + 2, i))

def chk(L):
	NN = 18
	BIT = [0] * (2 ** NN + 1)
	BITC = [0] * (2 ** NN + 1)
	SS = [0]
	CC = [0]

	def addrange(r0, x=1):
		r = r0
		SS[0] += x
		CC[0] += 1
		while r <= 2 ** NN:
			BIT[r] -= x
			BITC[r] -= 1
			r += r & -r

	def getvalue(r):
		a = 0
		c = 0
		while r != 0:
			a += BIT[r]
			c += BITC[r]
			r -= r & -r
		return (SS[0] + a, CC[0] + c)
	S = []
	for (a, b, i) in L:
		S.append(a)
		S.append(b)
	S = sorted(list(set(S)))
	D = {s: i for (i, s) in enumerate(S)}
	L = [(D[a], D[b], i) for (a, b, i) in L]
	s = 0
	L = sorted(L)
	m = -1
	for (a, b, i) in L:
		(v, c) = getvalue(a)
		s += v + c * W[i]
		addrange(b, W[i])
	return s
print('YES' if chk(A) == chk(B) else 'NO')


import sys
input = lambda : sys.stdin.readline().rstrip()
from bisect import bisect_right as br
ke = 1333333333
pp = 1000000000001003

def rand():
	global ke
	ke = ke ** 2 % pp
	return (ke >> 10) % (1 << 15) + (1 << 15)
N = int(input())
W = [rand() for _ in range(N)]
A = []
B = []
for i in range(N):
	(a, b, c, d) = map(int, input().split())
	A.append((a + 2, b + 3, i))
	B.append((c + 2, d + 3, i))

def chk(L):
	S = [1]
	for (a, b, i) in L:
		S.append(b)
	S = sorted(list(set(S)))
	D = {s: i for (i, s) in enumerate(S)}
	L = [(D[S[br(S, a) - 1]], D[b], i) for (a, b, i) in L]
	L = sorted(L)
	nn = 101010
	BIT = [0] * nn
	BITC = [0] * nn
	SS = [0]
	CC = [0]

	def addrange(r0, x=1):
		r = r0
		SS[0] += x
		CC[0] += 1
		while r <= nn:
			BIT[r] -= x
			BITC[r] -= 1
			r += r & -r

	def getvalue(r):
		a = 0
		c = 0
		while r != 0:
			a += BIT[r]
			c += BITC[r]
			r -= r & -r
		return (SS[0] + a, CC[0] + c)
	s = 0
	m = -1
	for (a, b, i) in L:
		(v, c) = getvalue(a)
		s += v + c * W[i]
		addrange(b, W[i])
	return s
print('YES' if chk(A) == chk(B) else 'NO')


import sys
input = lambda : sys.stdin.readline().rstrip()
ke = 133333333
pp = 1000000000001003

def rand():
	global ke
	ke = ke ** 2 % pp
	return (ke >> 10) % (1 << 20) + (1 << 20)
N = int(input())
W = [rand() for _ in range(N)]
(AL, AR, BL, BR) = ([], [], [], [])
for i in range(N):
	(a, b, c, d) = map(int, input().split())
	AL.append(a)
	AR.append(b)
	BL.append(c)
	BR.append(d)

def chk(L, R):
	S = sorted(list(set(L + R)))
	D = {s: i for (i, s) in enumerate(S)}
	L = [D[a] for a in L]
	R = [D[a] for a in R]
	X = [0] * 200200
	for (i, l) in enumerate(L):
		X[l] += W[i]
	for i in range(1, 200200):
		X[i] += X[i - 1]
	s = 0
	for (i, r) in enumerate(R):
		s += X[r] * W[i]
	return s
print('YES' if chk(AL, AR) == chk(BL, BR) else 'NO')