Problem:
 Score : 700 points    Problem Statement Snuke is playing a puzzle game.
In this game, you are given a rectangular board of dimensions R × C , filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (x_{i,1},y_{i,1}) and (x_{i,2},y_{i,2}) .  The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N .
Here, the curves may not go outside the board or cross each other.  Determine whether this is possible.      Constraints  1 ≤ R,C ≤ 10^8  1 ≤ N ≤ 10^5  0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)  0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)  All given points are distinct.  All input values are integers.         Input Input is given from Standard Input in the following format:  R  C  N  x_{1,1}  y_{1,1}  x_{1,2}  y_{1,2} : x_{N,1}  y_{N,1}  x_{N,2}  y_{N,2}       Output Print YES if the objective is achievable; print NO otherwise.        Sample Input 1 4 2 3
0 1 3 1
1 1 4 1
2 0 2 2      Sample Output 1 YES   The above figure shows a possible solution.       Sample Input 2 2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1      Sample Output 2 NO       Sample Input 3 5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1      Sample Output 3 YES       Sample Input 4 1 1 2
0 0 1 1
1 0 0 1      Sample Output 4 NO

Solution (Python):
from collections import deque

def f(x, y):
    if x == 0:
        return y
    if y == 0:
        return -x
    if x == r:
        return -(x + y)
    if y == c:
        return x + y

r, c, n = map(int, input().split())
xy = []
lxy = 0
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    d = []
    if min(x1, y1) == 0 or x1 == r or y1 == c:
        d.append([f(x1, y1), i])
    if min(x2, y2) == 0 or x2 == r or y2 == c:
        d.append([f(x2, y2), i])
    if len(d) == 2:
        xy.append(d[0])
        xy.append(d[1])
        lxy += 2
xy.sort()
q = deque()
lq = -1
for i in range(lxy):
    if not q:
        q.append(xy[i][1])
        lq += 1
    else:
        if q[lq] == xy[i][1]:
            q.pop()
            lq -= 1
        else:
            q.append(xy[i][1])
            lq += 1
print("YES" if not q else "NO")

Solution (Python):
from collections import deque

def f(x, y):
    if x == 0:
        return y
    if y == 0:
        return -x
    if x == r:
        return -(x + y)
    if y == c:
        return x + y

r, c, n = map(int, input().split())
xy = []
lxy = 0
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    d = []
    if min(x1, y1) == 0 or x1 == r or y1 == c:
        d.append([f(x1, y1), i])
    if min(x2, y2) == 0 or x2 == r or y2 == c:
        d.append([f(x2, y2), i])
    if len(d) == 2:
        xy.append(d[0])
        xy.append(d[1])
        lxy += 2
xy.sort()
q = deque()
for i in range(lxy):
    if not q:
        q.append(xy[i][1])
    else:
        if q[-1] == xy[i][1]:
            q.pop()
        else:
            q.append(xy[i][1])
print("YES" if not q else "NO")

Solution (Python):
import cmath


r, c, n = map(int, input().split())
lis = []


for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if (0 < x1 < r and 0 < y1 < c) or (0 < x2 < r and 0 < y2 < c):
        continue
    else:
        lis.append((i, x1 - r / 2 + (y1 - c / 2) * 1j))
        lis.append((i, x2 - r / 2 + (y2 - c / 2) * 1j))


lis.sort(key=lambda x: cmath.phase(x[1]))
stack = []


for i in lis:
    if stack == [] or stack[-1] != i[0]:
        stack.append(i[0])
    else:
        stack.pop()

        
if stack == []:
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
input = sys.stdin.readline

R, C, N = map(int, input().split())
right = []
top = []
left = []
bottom = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    
    if (x1 in (0, R) or y1 in (0, C)) and (x2 in (0, R) or y2 in (0, C)):
        if x1 == 0:
            top.append((y1, i))
        elif x1 == R:
            bottom.append((y1, i))
        elif y1 == 0:
            left.append((x1, i))
        elif y1 == C:
            right.append((x1, i))

        if x2 == 0:
            top.append((y2, i))
        elif x2 == R:
            bottom.append((y2, i))
        elif y2 == 0:
            left.append((x2, i))
        elif y2 == C:
            right.append((x2, i))
left.sort(key=lambda p: p[0])
bottom.sort(key=lambda p: p[0])
right.sort(key=lambda p: -p[0])
top.sort(key=lambda p: -p[0])
points = left + bottom + right + top
stack = []
for x, i in points:
    if not stack or stack[-1] != i:
        stack.append(i)
    else:
        stack.pop()
print('NO' if stack else 'YES')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

r,c,n = map(int,readline().split())
data = list(map(int,read().split()))
p = []
for i in range(n):
    x1,y1,x2,y2 = data[i*4:i*4+4]
    if((x1==0)|(x1==r)|(y1==0)|(y1==c))&((x2==0)|(x2==r)|(y2==0)|(y2==c)):
        for x,y in zip([x1,x2],[y1,y2]):
            num = 0
            if(x==0):
                num = y
            elif(x==r):
                num = r+2*c-y
            elif(y==0):
                num = 2*(r+c)-x
            else:
                num = c+x
            p.append([num,i])

p.sort()
d = []
for _,i in p:
    if(not d):
        d.append(i)
    else:
        right = d.pop()
        if(right != i):
            d.append(right)
            d.append(i)

if(len(d)==0):
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
input = sys.stdin.readline
R, C, N = map(int, input().split())
a = []

def conv(i, j):
  res = 0
  if i == 0:
    res = j
  elif j == C:
    res = C + i
  elif i == R:
    res = C + R + (C - j)
  elif j == 0: res = 2 * C + R + (R - i)
  else: res = -1
  return res

for i in range(N):
  x, y, u, v = map(int, input().split())
  d, dd = conv(x, y), conv(u, v)
  if d >= 0 and (dd >= 0):
    a.append((d, i))
    a.append((dd, i))
a.sort()
s = []
for _, i in a:
  if len(s) and s[-1] == i: s.pop()
  else: s.append(i)
if len(s): print("NO")
else: print("YES")

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

h,w,n, *xyxy = map(int,read().split())

def f(x,y):
    if y==0: return x
    elif x==h: return h+y
    elif y==w: return h+w+h-x
    else: return h+w+h+w-y    

m = iter(xyxy)
res = []
idx = 0
for x1,y1,x2,y2 in zip(m,m,m,m):
    if (x1*(h-x1)==0 or y1*(w-y1)==0) and (x2*(h-x2)==0 or y2*(w-y2)==0):
        res.append((f(x1,y1),idx))
        res.append((f(x2,y2),idx))
        idx += 1


res.sort()


st = []
for d,i in res:
    if st and st[-1] == i:
        st.pop()
    else:
        st.append(i)

if st:
    print("NO")
else:
    print("YES")

Solution (Python):
r, c, n = map(int, input().split())
l = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 == 0 or x1 == r or y1 == 0 or y1 == c) and (x2 == 0 or x2 == r or y2 == 0 or y2 == c):
        if x1 == 0:
            l.append((y1, i))
        elif y1 == c:
            l.append((c + x1, i))
        elif x1 == r:
            l.append((c * 2 + r - y1, i))
        else:
            l.append((r * 2 + c * 2 - x1, i))
        if x2 == 0:
            l.append((y2, i))
        elif y2 == c:
            l.append((c + x2, i))
        elif x2 == r:
            l.append((c * 2 + r - y2, i))
        else:
            l.append((r * 2 + c * 2 - x2, i))
l.sort()
s = []
d = [False] * n
for x, i in l:
    if d[i]:
        if s[-1] != i:
            print('NO')
            exit(0)
        s.pop()
    else:
        s.append(i)
        d[i] = True
print('YES')

Solution (Python):
r,c,n=map(int,input().split())
def po(x,y):
  if y==0:return x
  if x==r:return r+y
  if y==c:return r+c+(r-x)
  if x==0:return r+c+r+(c-y)
q=[]
for i in range(n):
  x1,y1,x2,y2=map(int,input().split())
  if (x1 in [0,r] or y1 in [0,c])and(x2 in [0,r] or y2 in [0,c]):
    q.append((po(x1,y1),i))
    q.append((po(x2,y2),i))
if len(q)==0:exit(print("YES"))
q.sort()
d=[]
for _,i in q:
  if len(d)==0:d.append(i)
  elif d[-1]==i:del d[-1]
  else:d.append(i)
if len(d)==0:print('YES')
else:print('NO')

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    R, C, N = LI()
    P = []
    P1 = []; P2 = []; P3 = []; P4 = []
    index = 0
    for i in range(N):
        x1,y1,x2,y2 = LI()
        if (x1 not in (0,R)) and (y1 not in (0,C)):
            continue
        if (x2 not in (0,R)) and (y2 not in (0,C)):
            continue

        if x1==0:
            P1.append((x1, y1, index))
        elif y1 == C:
            P2.append((x1, y1, index))
        elif x1==R:
            P3.append((x1, y1, index))
        else:
            P4.append((x1, y1, index))

        if x2==0:
            P1.append((x2, y2, index))
        elif y2 == C:
            P2.append((x2, y2, index))
        elif x2==R:
            P3.append((x2, y2, index))
        else:
            P4.append((x2, y2, index))
        index += 1
    P1.sort(key=lambda x:x[1])
    P2.sort()
    P3.sort(key=lambda x:x[1], reverse=True)
    P4.sort(reverse=True)
    for _,_,p in P1:
        P.append(p)
    for _,_,p in P2:
        P.append(p)
    for _,_,p in P3:
        P.append(p)
    for _,_,p in P4:
        P.append(p)
    

    que = deque()
    for index in P:
        if que:
            now = que.pop()
            if index==now:
                continue
            que.append(now)
            que.append(index)
        else:
            que.append(index)
    if que:
        print("NO")
    else:
        print("YES")
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import sys
input = sys.stdin.readline

def main():
  r, c, n = map(int, input().split())
  L = []
  def trans(x, y):
    z = None
    if x == 0:
      z = y
    if y == c:
      z = c + x
    if x == r:
      z = c + r + c - y
    if y == 0:
      z = 2*r + 2*c - x
    return z

  for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    z1 = trans(x1, y1)
    z2 = trans(x2, y2)
    if z1 is not None and z2 is not None:
      L.append((z1, z2))
      L.append((z2, z1))
  L.sort()
  cnt = 0
  D = dict()
  for z1, z2 in L:
    if z1 < z2:
      cnt += 1
      D[z1] = cnt
    else:
      if D[z2] != cnt:
        print("NO")
        exit()
      cnt -= 1
  print("YES")
if __name__ == "__main__":
  main()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
  r, c, n = map(int, input().split())
  L = []
  def trans(x, y):
    z = None
    if x == 0:
      z = y
    if y == c:
      z = c + x
    if x == r:
      z = c + r + c - y
    if y == 0:
      z = 2*r + 2*c - x
    return z

  for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    z1 = trans(x1, y1)
    z2 = trans(x2, y2)
    if z1 is not None and z2 is not None:
      L.append((z1, z2))
      L.append((z2, z1))
  L.sort()
  cnt = 0
  D = dict()
  for z1, z2 in L:
    if z1 < z2:
      cnt += 1
      D[z1] = cnt
    else:
      if D[z2] != cnt:
        print("NO")
        exit()
      cnt -= 1
  print("YES")
if __name__ == "__main__":
  main()

Solution (Python):
import sys
input = sys.stdin.readline

r, c, n = map(int, input().split())
L = []
def trans(x, y):
  z = None
  if x == 0:
    z = y
  if y == c:
    z = c + x
  if x == r:
    z = c + r + c - y
  if y == 0:
    z = 2*r + 2*c - x
  return z

for _ in range(n):
  x1, y1, x2, y2 = map(int, input().split())
  z1 = trans(x1, y1)
  z2 = trans(x2, y2)
  if z1 is not None and z2 is not None:
    if z1 > z2:
      z1, z2 = z2, z1
    L.append((z1, z2))
    L.append((z2, z1))
L.sort()
cnt = 0
D = dict()
for z1, z2 in L:
  if z1 < z2:
    cnt += 1
    D[z1] = cnt
  else:
    if D[z2] != cnt:
      print("NO")
      exit()
    cnt -= 1
print("YES")

Solution (Python):
R, C, N = map(int, input().split())
edge = []


def F(x, y):
    if x == 0:
        return y
    if y == C:
        return C + x
    if x == R:
        return R + C * 2 - y
    if y == 0:
        return 2 * R + 2 * C - x
    return -1


for i in range(1, N + 1):
    x1, y1, x2, y2 = map(int, input().split())
    d1 = F(x1, y1)
    d2 = F(x2, y2)
    if d1 < 0:
        continue
    if d2 < 0:
        continue
    edge.append((d1, i))
    edge.append((d2, i))

edge.sort()
stack = []
used = [False] * (N + 1)

ans = "YES"
for _, x in edge:
    if not used[x]:
        used[x] = True
        stack.append(x)
    else:
        y = stack.pop()
        if x != y:
            ans = "NO"
            break

print(ans)

Solution (Python):
def main():
    from bisect import bisect_left as bl

    class BIT():
        def __init__(self, member):
            self.member_list = sorted(member)
            self.member_dict = {v: i+1 for i, v in enumerate(self.member_list)}
            self.n = len(member)
            self.maxmember = self.member_list[-1]
            self.minmember = self.member_list[0]
            self.maxbit = 2**(len(bin(self.n))-3)
            self.bit = [0]*(self.n+1)
            self.allsum = 0

        
        def add(self, i, v):
            x = self.member_dict[i]
            self.allsum += v
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k = 0, self.maxbit
            while k:
                if x+k <= self.n and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x

        
        def greater(self, v):
            if v > self.maxmember:
                return None
            p = self.sum(bl(self.member_list, v))
            if p == self.allsum:
                return None
            return self.member_list[self.lowerbound(p+1)]

        
        def smaller(self, v):
            if v < self.minmember:
                return None
            b = bl(self.member_list, v)
            if b == self.n:
                b -= 1
            elif self.member_list[b] != v:
                b -= 1
            p = self.sum(b+1)
            if p == 0:
                return None
            return self.member_list[self.lowerbound(p)]

    r, c, n = map(int, input().split())
    xyzw = [list(map(int, input().split())) for _ in [0]*n]
    outer = []
    for x, y, z, w in xyzw:
        if x in [0, r] or y in [0, c]:
            if z in [0, r] or w in [0, c]:
                if y == 0:
                    p = x
                elif x == r:
                    p = r+y
                elif y == c:
                    p = 2*r+c-x
                else:
                    p = 2*r+2*c-y
                if w == 0:
                    q = z
                elif z == r:
                    q = r+w
                elif w == c:
                    q = 2*r+c-z
                else:
                    q = 2*r+2*c-w
                if p > q:
                    p, q = q, p
                outer.append((p, q))

    member = [i for i, j in outer]+[j for i, j in outer]+[-1]+[2*r+2*c+1]
    bit = BIT(member)
    bit.add(-1, 1)
    bit.add(2*r+2*c+1, 1)

    outer.sort(key=lambda x: x[0]-x[1])
    for a, b in outer:
        if bit.greater(a) < b:
            print("NO")
            return
        bit.add(a, 1)
        bit.add(b, 1)
    print("YES")


main()

Solution (Python):
def main():
    from bisect import bisect_left as bl

    class BIT():
        def __init__(self, member):
            self.member_list = sorted(member)
            self.member_dict = {v: i+1 for i, v in enumerate(self.member_list)}
            self.n = len(member)
            self.maxmember = self.member_list[-1]
            self.minmember = self.member_list[0]
            self.maxbit = 2**(len(bin(self.n))-3)
            self.bit = [0]*(self.n+1)
            self.allsum = 0

        
        def add(self, i, v):
            x = self.member_dict[i]
            self.allsum += v
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k = 0, self.maxbit
            while k:
                if x+k <= self.n and self.bit[x+k] < w:
                    w -= self.bit[x+k]
                    x += k
                k //= 2
            return x

        
        def greater(self, v):
            if v > self.maxmember:
                return None
            p = self.sum(bl(self.member_list, v))
            if p == self.allsum:
                return None
            return self.member_list[self.lowerbound(p+1)]

        
        def smaller(self, v):
            if v < self.minmember:
                return None
            b = bl(self.member_list, v)
            if b == self.n:
                b -= 1
            elif self.member_list[b] != v:
                b -= 1
            p = self.sum(b+1)
            if p == 0:
                return None
            return self.member_list[self.lowerbound(p)]

    r, c, n = map(int, input().split())
    xyzw = [list(map(int, input().split())) for _ in [0]*n]
    outer = []
    for x, y, z, w in xyzw:
        if x in [0, r] or y in [0, c]:
            if z in [0, r] or w in [0, c]:
                if y == 0:
                    p = x
                elif x == r:
                    p = r+y
                elif y == c:
                    p = 2*r+c-x
                else:
                    p = 2*r+2*c-y
                if w == 0:
                    q = z
                elif z == r:
                    q = r+w
                elif w == c:
                    q = 2*r+c-z
                else:
                    q = 2*r+2*c-w
                if p > q:
                    p, q = q, p
                outer.append((p, q))

    member = [i for i, j in outer]+[j for i, j in outer]+[-1]+[2*r+2*c+1]
    bit = BIT(member)
    bit.add(-1, 1)
    bit.add(2*r+2*c+1, 1)

    outer.sort(key=lambda x: x[0]-x[1])
    for a, b in outer:
        if bit.greater(a) < b:
            print("NO")
            return
        bit.add(a, 1)
        bit.add(b, 1)
    print("YES")


main()

Solution (Python):
import sys

input=sys.stdin.readline

R,C,N=map(int,input().split())

def is_on_edge(x,y):
    return x==0 or x==R or y==0 or y==C

line=[]
for i in range(0,N):
    x1,y1,x2,y2=map(int,input().split())
    if is_on_edge(x1,y1) and is_on_edge(x2,y2):
        line.append([x1,y1,x2,y2])

n=len(line)
query=[]
for i in range(n):
    x1,y1,x2,y2=line[i]
    if y1==0:
        query.append([x1,i])
    elif x1==R:
        query.append([R+y1,i])
    elif y1==C:
        query.append([R+C+(R-x1),i])
    else:
        query.append([2*R+2*C-y1,i])

    if y2==0:
        query.append([x2,i])
    elif x2==R:
        query.append([R+y2,i])
    elif y2==C:
        query.append([R+C+(R-x2),i])
    else:
        query.append([2*R+2*C-y2,i])

query.sort(reverse=True)
que=[]
dic=[0 for i in range(n)]
while query:
    t,num=query.pop()
    if dic[num]==0:
        que.append(num)
        dic[num]=1
    else:
        if que[-1]!=num:
            print("NO")
            exit()
        else:
            dic[num]=2
            que.pop()
print("YES")

Solution (Python):
w, h, n = map(int, input().split())

pos = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 in [0, w] or y1 in [0, h]) and (x2 in [0, w] or y2 in [0, h]):
        pos.append((x1, y1, i))
        pos.append((x2, y2, i))

pos.sort(key=lambda v: v[0]) 
edge = [v[-1] for v in pos if v[1] == 0 and v[0] != 0]

pos.sort(key=lambda v: v[1]) 
edge += [v[-1] for v in pos if v[0] == w and v[1] != 0]

pos.sort(key=lambda v: v[0], reverse=True) 
edge += [v[-1] for v in pos if v[1] == h and v[0] != w]

pos.sort(key=lambda v: v[1], reverse=True) 
edge += [v[-1] for v in pos if v[0] == 0 and v[1] != h]












hist = [None] * n
step = 0
for v in edge:
    if hist[v] is None:
        hist[v] = step + 1
        step += 1
    else:
        if hist[v] != step:
            print("NO")
            break
        step -= 1
else:
    print("YES")

Solution (Python):
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from operator import itemgetter


def compress(array):
    """座標圧縮したリストを返す"""
    set_ = set()
    for num in array:
        set_.add(num[0])
        set_.add(num[1])
    array2 = sorted(set_)
    memo = {value: index for index, value in enumerate(array2)}
    for i in range(len(array)):
        array[i] = (memo[array[i][0]], memo[array[i][1]])
    return array

def on_line(x, y):
    return x == 0 or x == r or y == 0 or y == c

def val(x, y):
    if y == 0:
        return x
    if x == r:
        return r + y
    if y == c:
        return r + c + (r - x)
    if x == 0:
        return r + c + r + (c - y)

r, c, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

res = []
for i in range(n):
    x1, y1, x2, y2 = info[i]
    if on_line(x1, y1) and on_line(x2, y2):
        left = val(x1, y1)
        right = val(x2, y2)
        if left > right:
            left, right = right, left
        res.append((left, right))


res = sorted(res, key=itemgetter(1))
res = compress(res)

bit = BIT(2 * len(res))
for left, right in res:
    if bit.get_val(left) != 0:
        print("NO")
        exit()
    else:
        bit.add(left, right + 1, 1)
print("YES")

Solution (Python):
from operator import itemgetter
import collections
r,c,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
e1=[];e2=[];e3=[];e4=[]
for i in range(n):
  if (l[i][0]==0 or l[i][0]==r or l[i][1]==0 or l[i][1]==c) and (l[i][2]==0 or l[i][2]==r or l[i][3]==0 or l[i][3]==c):
    if l[i][0]==0 and l[i][1]!=c:
      e1.append([i+1,l[i][0],l[i][1]])
    elif l[i][1]==c and l[i][0]!=r:
      e2.append([i+1,l[i][0],l[i][1]])
    elif l[i][0]==r and l[i][1]!=0:
      e3.append([i+1,l[i][0],l[i][1]])
    else:
      e4.append([i+1,l[i][0],l[i][1]])
    if l[i][2]==0 and l[i][3]!=c:
      e1.append([i+1,l[i][2],l[i][3]])
    elif l[i][3]==c and l[i][2]!=r:
      e2.append([i+1,l[i][2],l[i][3]])
    elif l[i][2]==r and l[i][3]!=0:
      e3.append([i+1,l[i][2],l[i][3]])
    else:
      e4.append([i+1,l[i][2],l[i][3]])
e1=sorted(e1,key=itemgetter(2))
e2=sorted(e2,key=itemgetter(1))
e3=sorted(e3,key=itemgetter(2))
e4=sorted(e4,key=itemgetter(1))
e3.reverse()
e4.reverse()
e=e1+e2+e3+e4

q=[]
q=collections.deque(q)
for i in range(len(e)):
  if len(q)==0:
    q.append(e[i][0])
  else:
    if q[-1]==e[i][0]:
      q.pop()
    else:
      q.append(e[i][0])
if len(q)==0:
  print('YES')
else:
  print('NO')

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

def calc(a, b):
    if b == 0: return a
    if a == R: return b + R
    if b == C: return R + C + (R - a)
    if a == 0: return R + C + R + (C - b)

R, C, N = map(int, input().split())
A = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 == 0 or x1 == R or y1 == 0 or y1 == C) and (x2 == 0 or x2 == R or y2 == 0 or y2 == C):
        A.append((calc(x1, y1), i))
        A.append((calc(x2, y2), i))

A = [l[1] for l in sorted(A, key = lambda x: x[0])]
B = []

while A:
    while len(B) and A[-1] == B[-1]:
        A.pop()
        B.pop()
    if A:
        B.append(A.pop())

print("NO" if len(B) else "YES")

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

def calc(a, b):
    if b == 0: return a
    if a == R: return b + R
    if b == C: return R + C + (R - a)
    if a == 0: return R + C + R + (C - b)

R, C, N = map(int, input().split())
A = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 == 0 or x1 == R or y1 == 0 or y1 == C) and (x2 == 0 or x2 == R or y2 == 0 or y2 == C):
        A.append((calc(x1, y1), i))
        A.append((calc(x2, y2), i))

A = [l[1] for l in sorted(A, key = lambda x: x[0])]
B = []

while A:
    while len(B) and A[-1] == B[-1]:
        A.pop()
        B.pop()
    if A:
        B.append(A.pop())

print("NO" if len(B) else "YES")

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
R, C, N = map(int, input().split())
X = {0, R}
Y = {0, C}

Z = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 == 0 or x1 == R or y1 == 0 or y1 == C) and (x2 == 0 or x2 == R or y2 == 0 or y2 == C):
        Z.append((x1, y1, x2, y2))
        X.add(x1)
        X.add(x2)
        Y.add(y1)
        Y.add(y2)

DX = {a: i for i, a in enumerate(sorted(list(X)))}
DY = {a: i for i, a in enumerate(sorted(list(Y)))}
R, C = DX[R], DY[C]

def calc(a, b):
    if b == 0:
        return a
    if a == R:
        return b + R
    if b == C:
        return R + C + (R - a)
    if a == 0:
        return R + C + R + (C - b)

A = []
for i, (x1, y1, x2, y2) in enumerate(Z):
    x3, y3, x4, y4 = DX[x1], DY[y1], DX[x2], DY[y2]
    A.append((calc(x3, y3), i))
    A.append((calc(x4, y4), i))

A = [l[1] for l in sorted(A, key = lambda x: x[0])]
B = []

while A:
    while len(B) and A[-1] == B[-1]:
        A.pop()
        B.pop()
    if A:
        B.append(A.pop())

print("NO" if len(B) else "YES")

Solution (Python):
r, c, n = map(int, input().split())
points = []
xx = [0, r]
yy = [0, c]
def add(x, y):
    if x == 0:
        points.append(r*2+c+c-y)
    elif x == r:
        points.append(r+y)
    elif y == 0:
        points.append(x)
    else:
        points.append(r+c+r-x)
for i in range(n):
    x0, y0, x1, y1 = map(int, input().split())
    if (x0 in xx or y0 in yy) and (x1 in xx or y1 in yy):
        add(x0, y0)
        add(x1, y1)
index = list(range(len(points)))
index.sort(key = lambda a:points[a])
que = []
flag = True
for i in index:
    if que and que[-1]//2 == i//2:
        que.pop()
    else:
        que.append(i)
if que:
    print('NO')
else:
    print('YES')

Solution (Python):
import sys
input = sys.stdin.readline
r,c,n = map(int,input().split())
xy = [list(map(int,input().split())) for i in range(n)]
ls = []
for x1,y1,x2,y2 in xy:
  if (x1 in (0,r) or y1 in (0,c)) and (x2 in (0,r) or y2 in (0,c)):
    k = []
    for x,y in ((x1,y1),(x2,y2)):
      if x == 0:
        s = 2*r+2*c-y
      if x == r:
        s = r+y
      if y == 0:
        s = x
      if y == c:
        s = 2*r+c-x
      k.append(s)
    t = len(ls)//2+1
    ls.append((k[0],t))
    ls.append((k[1],t))
if not ls:
  print("YES")
  exit()
ls.sort()
lsi = list(map(list,zip(*ls)))[1]
m = len(lsi)
stack = []
for i in lsi:
  if not stack:
    stack.append(i)
  else:
    if stack[-1] == i:
      stack.pop()
    else:
      stack.append(i)
if stack:
  print("NO")
else:
  print("YES")

Solution (Python):
R, C, N = map(int, input().split())
pts = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    zs = []
    for x, y in [(x1, y1), (x2, y2)]:
        if y == 0:
            zs.append((x, i))
        elif x == R:
            zs.append((R+y, i))
        elif y == C:
            zs.append((2*R+C-x, i))
        elif x == 0:
            zs.append((2*R+2*C-y, i))
    if len(zs) == 2:
        pts += zs

pts.sort()

stack = []
for z, i in pts:
    if not stack:
        stack.append(i)
    else:
        if stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)

if not stack:
    print('YES')
else:
    print('NO')

Solution (Python):
import os
import sys
from collections import deque, Counter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



R, C, N = list(map(int, sys.stdin.buffer.readline().split()))
XY = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]




p1 = []
p2 = []
p3 = []
p4 = []
for i, (x1, y1, x2, y2) in enumerate(XY):
    for x, y in ((x1, y1), (x2, y2)):
        if y == 0:
            p1.append((x, i))
        elif x == R:
            p2.append((y, i))
        elif y == C:
            p3.append((x, i))
        elif x == 0:
            p4.append((y, i))

p1.sort()
p2.sort()
p3.sort(reverse=True)
p4.sort(reverse=True)

points = p1 + p2 + p3 + p4
counts = Counter([i for _, i in points])
que = deque()
for _, i in points:
    if counts[i] <= 1:
        continue
    if que and que[-1] == i:
        que.pop()
    else:
        que.append(i)

while len(que) >= 2 and que[0] == que[-1]:
    que.popleft()
    que.pop()

ok = len(que) == 0
if ok:
    print('YES')
else:
    print('NO')

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter

X, Y, N = map(int, input().split())
U = []
D = []
R = []
L = []

def mustconsider(x, y):
    return (x in [0, X]) or (y in [0, Y])

def divide(x, y, i):
    if x == 0 and y != Y:
        L.append((y, i))
    if x == X and y != 0:
        R.append((y, i))
    if y == 0 and x != 0:
        D.append((x, i))
    if y == Y and x != X:
        U.append((x, i))

for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if mustconsider(x1, y1) and mustconsider(x2, y2):
        divide(x1, y1, i)
        divide(x2, y2, i)

D.sort()
R.sort()
U.sort(reverse=True)
L.sort(reverse=True)

Arounds = []
for _, ind in D:
    Arounds.append(ind)
for _, ind in R:
    Arounds.append(ind)
for _, ind in U:
    Arounds.append(ind)
for _, ind in L:
    Arounds.append(ind)

stack = []
for a in Arounds:
    if not stack:
        stack.append(a)
    else:
        if stack[-1] == a:
            stack.pop()
        else:
            stack.append(a)

print("YES" if not stack else "NO")