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



Sample input:
4 2 3
0 1 3 1
1 1 4 1
2 0 2 2


Sample output:
YES

Submission status: Accepted

Solution code:
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 both points are on the edge
    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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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()
#print(res)

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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)
    #print(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
"""

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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]) # top →
edge = [v[-1] for v in pos if v[1] == 0 and v[0] != 0]

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

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

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

# for i in range(len(edge) - 1):
#     if edge[i] == edge[i + 1]:
#         break
# for j in range(len(edge) // 2):
#     if edge[(i + j + 1) % n] != edge[(i - j + n) % n]:
#         print("NO")
#         break
# else:
#     print("YES")

# print(edge)
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
R,C,N = list(map(int,input().split()))

point = []

def XtoZ(x,y):
    if x==0:
        if y==0:
            return 0
        else:
            return 2*R + 2*C - y
    elif x==R:
        return R + y
    elif y==0:
        return x
    elif y==C:
        return 2*R + C - x

for i in range(N):
    x1,y1,x2,y2 = list(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)):
        point.append([XtoZ(x1,y1),i])
        point.append([XtoZ(x2,y2),i])

point.sort(key = lambda x:x[0])

flag = [0]*N

from collections import deque

Q = deque()

flag = [True]*N
flag2=False
for p in point:
    if flag[p[1]]:
        Q.append(p[1])
        flag[p[1]] = False
    else:
        if Q.pop()!=p[1]:
            flag2=True
            break

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

Submission status: Accepted

Solution code:

def hantei(x,y):

    if y == 0:
        return "l"
    elif x == R:
        return "d"
    elif y == C:
        return "r"
    elif x == 0:
        return "u"

    return "n"

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

u = []
l = []
d = []
r = []

for i in range(N):

    X1,Y1,X2,Y2 = map(int,input().split())

    if hantei(X1,Y1) != "n" and hantei(X2,Y2) != "n":


        if hantei(X1,Y1) == "l":
            l.append([X1,Y1,i])
        elif hantei(X1,Y1) == "d":
            d.append([X1,Y1,i])
        elif hantei(X1,Y1) == "r":
            r.append([X1,Y1,i])
        elif hantei(X1,Y1) == "u":
            u.append([X1,Y1,i])

        X1 = X2
        Y1 = Y2
    
        if hantei(X1,Y1) == "l":
            l.append([X1,Y1,i])
        elif hantei(X1,Y1) == "d":
            d.append([X1,Y1,i])
        elif hantei(X1,Y1) == "r":
            r.append([X1,Y1,i])
        elif hantei(X1,Y1) == "u":
            u.append([X1,Y1,i])

l.sort()
d.sort()
r.sort()
r.reverse()
u.sort()
u.reverse()

ps = []
for i in l:
    ps.append(i[2])
for i in d:
    ps.append(i[2])
for i in r:
    ps.append(i[2])
for i in u:
    ps.append(i[2])

q = []

for i in ps:
    if len(q) > 0 and q[-1] == i:
        del q[-1]
    else:
        q.append(i)

if len(q) == 0:
    print ("YES")
else:
    print ("NO")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    h, w, n = MI()
    points = []
    cnt = 0
    # 2点とも周上にある組のみ残す
    # 原点（左上）から反時計回りに移動した距離と点の通し番号を記録
    for _ in range(n):
        i0, j0, i1, j1 = MI()
        if (0 < i0 < h and 0 < j0 < w) or (0 < i1 < h and 0 < j1 < w): continue
        for i, j in [(i0, j0), (i1, j1)]:
            if j == 0 or i == h:
                d = i + j
            else:
                d = 2 * (h + w) - i - j
            points.append([d, cnt])
        cnt += 1
    points.sort()
    first = [True] * cnt
    visited = []
    # ABABのように２つの区間がずれて重なっていたらNO
    # ABBAのように完全に含まれるのはセーフ
    for d, pi in points:
        if first[pi]:
            visited.append(pi)
            first[pi] = False
        else:
            last_pi = visited.pop()
            if pi != last_pi:
                print("NO")
                exit()
    print("YES")

main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def check(x,y):
        return (x == 0)|(x == w)|(y == 0)|(y == h)

    w,h,n = LI()
    px0 = []
    pxw = []
    py0 = []
    pyh = []
    for i in range(1,n+1):
        x,y,s,t = LI()
        if check(x,y)&check(s,t):
            if x == 0:
                px0.append((y,i))
            elif x == w:
                pxw.append((-y,i))
            elif y == 0:
                py0.append((-x,i))
            else:
                pyh.append((x,i))
            if s == 0:
                px0.append((t,i))
            elif s == w:
                pxw.append((-t,i))
            elif t == 0:
                py0.append((-s,i))
            else:
                pyh.append((s,i))
    px0.sort()
    pxw.sort()
    py0.sort()
    pyh.sort()
    p = px0+pyh+pxw+py0
    q = deque()
    for x, i in p:
        if q:
            qi = q.pop()
            if qi != i:
                q.append(qi)
                q.append(i)
        else:
            q.append(i)
    if q:
        print("NO")
    else:
        print("YES")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


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)


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

def solve(x1, y1):
    if y1 == 0:
        return x1
    if x1 == r:
        return r + y1
    if y1 == c:
        return r + c + (r-x1)
    if x1 == 0:
        return r + c + r + (c-y1)

li = []
for i in range(n):
    x1, y1, x2, y2 = info[i]
    if (x1 % r == 0 or y1 % c == 0) and (x2 % r == 0 or y2 % c == 0):
        pos1, pos2 = solve(x1, y1), solve(x2, y2)
        li.append((pos1, i))
        li.append((pos2, i))

li = sorted(li)
q = deque([])
for i in range(len(li)):
    _, j = li[i]
    if q and q[-1] == j:
        q.pop()
    else:
        q.append(j)
if q:
    print("NO")
else:
    print("YES")

Submission status: Accepted

Solution code:
import random
import sys
input = sys.stdin.readline


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)


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

def solve(x1, y1):
    if y1 == 0:
        return x1
    if x1 == r:
        return r + y1
    if y1 == c:
        return r + c + (r-x1)
    if x1 == 0:
        return r + c + r + (c-y1)

def compress(array):
    set_ = set([])
    for i in range(len(array)):
        a, b = array[i]
        set_.add(a)
        set_.add(b)
    memo = {value : index for index, value in enumerate(sorted(list(set_)))}
    max_ = 0
    for i in range(len(array)):
        array[i][0] = memo[array[i][0]]
        array[i][1] = memo[array[i][1]]
        max_ = max(max_, *array[i])
    return max_, array

query = []
for i in range(n):
    x1, y1, x2, y2 = info[i]
    if (x1 % r == 0 or y1 % c == 0) and (x2 % r == 0 or y2 % c == 0):
        pos1, pos2 = solve(x1, y1), solve(x2, y2)
        if pos1 > pos2:
            pos1, pos2 = pos2, pos1
        query.append([pos1, pos2 + 1])

m, query = compress(query)
bit = BIT(m)  
for i in range(len(query)):
    begin, end = query[i]
    if bit.get_val(begin) != bit.get_val(end - 1):
        print("NO")
        exit()
    tmp = random.randrange(0, 10**18)
    bit.add(begin, end, tmp)
print("YES")