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: Wrong Answer

Solution code:
R,C,n=map(int,raw_input().split())
pair=[map(int,raw_input().split()) for _ in xrange(n)]
u=[]
r=[]
d=[]
l=[]
for i in xrange(n):
    x1,y1,x2,y2=pair[i]
    if 0<x1<R and 0<y1<C:continue
    if 0<x2<R and 0<y2<C:continue
    if x1==0:
        u.append([y1,i])
    if x1==R:
        d.append([y1,i])
    if y1==0:
        if x1!=0 and x1!=R:
            l.append([x1,i])
    if y1==C:
        if x1!=0 and x1!=R:
            r.append([x1,i])
    if x2==0:
        u.append([y2,i])
    if x2==R:
        d.append([y2,i])
    if y2==0:
        if x2!=0 and x2!=R:
            l.append([x2,i])
    if y2==C:
        if x2!=0 and x2!=R:
            r.append([x2,i])
u.sort()
r.sort()
d.sort(reverse=True)
l.sort(reverse=True)
urdl=u+r+d+l
if len(urdl)==0:
    print "YES"
    exit()
for i in xrange(len(urdl)-1):
    if urdl[i][1]!=urdl[i+1][1]:
        print "NO"
        exit()
print "YES"

Submission status: Wrong Answer

Solution code:
r,c,n=map(int,raw_input().split())
pair=[map(int,raw_input().split()) for _ in xrange(n)]
u=[]
r=[]
d=[]
l=[]
for i in xrange(n):
    x1,y1,x2,y2=pair[i]
    if 0<x1<r and 0<y1<c:continue
    if 0<x2<r and 0<y2<c:continue
    if x1==0:
        u.append(y1)
    if x1==r:
        d.append(y1)
    if y1==0:
        if x1!=0 and x1!=r:
            l.append(x1)
    if y1==c:
        if x1!=0 and x1!=r:
            r.append(x1)

    if x2==0:
        u.append(y2)
    if x2==r:
        d.append(y2)
    if y2==0:
        if x2!=0 and x2!=r:
            l.append(x2)
    if y2==c:
        if x2!=0 and x2!=r:
            r.append(x2)
u.sort()
r.sort()
d.sort()
l.sort()
urdl=u+r+d+l
if len(urdl)==0:
    print "YES"
    exit()
for i in xrange(len(urdl)-1):
    if urdl[i]!=urdl[i+1]:
        print "NO"
        exit()
print "YES"

Submission status: Wrong Answer

Solution code:
r, c, n = map(int, raw_input().split())
x1 = []
y1 = []
x2 = []
y2 = []
for i in xrange(n): 
  xx1, yy1, xx2, yy2 = map(int, raw_input().split())
  x1.append(xx1)
  y1.append(yy1)
  x2.append(xx2)
  y2.append(yy2)

t = []
b = []
l = []
r = []

def add(x, y, i):
  if x == 0:
    t.append((i, y))
  elif x == r:
    b.append((i, y))
  elif y == 0:
    l.append((i, x))
  elif y == c:
    r.append((i, x))


for i in xrange(n):
  add(x1[i], y1[i], i)
  add(x2[i], y2[i], i)

t = sorted(t, key=lambda x : x[1])    
r = sorted(r, key=lambda x : x[1])
b = sorted(b, key=lambda x : x[1], reverse=True)
l = sorted(l, key=lambda x : x[1], reverse=True)

lis = []
lis.extend(t)
lis.extend(r)
lis.extend(b)
lis.extend(l)

lis = map(lambda x : x[0], lis)

cnt = {}
for i in lis:
  if not i in cnt:
    cnt[i] = 0
  cnt[i] += 1

lis = filter(lambda x : cnt[x] == 2, lis)

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

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

Submission status: Wrong Answer

Solution code:
r,c,n=map(int,raw_input().split())
pair=[map(int,raw_input().split()) for _ in xrange(n)]
u=[]
r=[]
d=[]
l=[]
for i in xrange(n):
    x1,y1,x2,y2=pair[i]
    if 0<x1<r and 0<y1<c:continue
    if 0<x2<r and 0<y2<c:continue
    if x1==0:
        u.append(i)
    if x1==r:
        d.append(i)
    if y1==0:
        if x1==0 or x1==r:continue
        l.append(i)
    if y1==c:
        if x1==0 or x1==r:continue
        r.append(i)

    if x2==0:
        u.append(i)
    if x2==r:
        d.append(i)
    if y2==0:
        if x2==0 or x2==r:continue
        l.append(i)
    if y2==c:
        if x2==0 or x2==r:continue
        r.append(i)
urdl=u+r+d+l
for i in xrange(len(urdl)-1):
    if urdl[i]!=urdl[i+1]:
        print "NO"
        exit()
print "YES"

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))


R, C, N = rli()
lis = []
idx = 0
i = 0
for j in range(N):
    x1, y1, x2, y2 = rli()
    if((x1 % R == 0 or y1 % C == 0) and (x2 % R == 0 or y2 % C == 0)):
        i += 1
        for _ in range(2):
            if(y1 == 0):
                lis.append([x1, i])
            elif(x1 == R):
                lis.append([R+y1, i])
            elif(y1 == C):
                lis.append([2*R+C-x1, i])
            elif(x1 == 0):
                lis.append([2*R+2*C-y1, i])
            x1 = x2
            y1 = y2
lis.sort()
st = 0
g = 0
for k in range(2*i-1):
    if(lis[k][1] != lis[k+1][1]):
        break
    i -= 1
    st += 2
for k in range(2*i-1):
    if(lis[k][1] != lis[k+1][1]):
        break
    i -= 1
    g += 2


ans = True
for k in range(i):
    if(lis[k+st][1] != lis[-(k+1-g)][1]):
        ans = False

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

Submission status: Wrong Answer

Solution code:
r,c,n=map(int,raw_input().split())
pair=[map(int,raw_input().split()) for _ in xrange(n)]
tate=True
yoko=True
for i in xrange(n):
    x1,y1,x2,y2=pair[i]
    if x1>x2:x1,x2=x2,x1
    if y1>y2:y1,y2=y2,y1
    if x1==0 and x2==r:
        tate=False
    if y1==0 and y2==c:
        yoko=False
if tate or  yoko:
    print "YES"
else:
    print "NO"

Submission status: Wrong Answer

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))


R, C, N = rli()
lis = []
idx = 0
i = 0
for j in range(N):
    x1, y1, x2, y2 = rli()
    if((x1 % R == 0 or y1 % C == 0) and (x2 % R == 0 or y2 % C == 0)):
        i += 1
        for _ in range(2):
            if(y1 == 0):
                lis.append([x1, i])
            elif(x1 == R):
                lis.append([R+y1, i])
            elif(y1 == C):
                lis.append([2*R+C-x1, i])
            elif(x1 == 0):
                lis.append([2*R+2*C-y1, i])
            x1 = x2
            y1 = y2
lis.sort()

ans = True
for k in range(i):
    if(lis[k][1] != lis[-(k+1)][1]):
        ans = False

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()



def main():
    R,C,N = LI()
    a = []
    def ff(x,y):
        if x == 0:
            return (0,y)
        if x == R:
            return (R,-y)
        if y == 0:
            return (R+1, -x)
        return (1, x)

    for _ in range(N):
        x1,y1,x2,y2 = LI()
        if (0 < x1 < R and 0 < y1 < C) or (0 < x2 < R and 0 < y2 < C):
            continue
        a.append((ff(x1,y1),_))
        a.append((ff(x2,y2),_))
    a.sort()
    b = [a[i][1] for i in range(len(a))]
    ti = 0
    while len(b) > 2:
        l = len(b)
        f = True
        for i in range(l):
            if b[(ti+i)%l] == b[(ti+i+1)%l]:
                if (ti+i+1)%l == 0:
                    b = b[1:-1]
                else:
                    b = b[:(ti+i)%l] + b[(ti+i+2):]
                f = False
                ti = (ti+i) % l
                break
        if f:
            break

    if len(b) > 2:
        return 'NO'
    return 'YES'

print(main())

Submission status: Time Limit Exceeded

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

        # 要素iにvを追加する
        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)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        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

        # vに一番近いv以上の値を求める
        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)]

        # vに一番近いv以下の値を求める
        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()

Submission status: Time Limit Exceeded

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():
    import operator
    class SegmentTree:
        def __init__(self, size, default, op = operator.add):
            self.size = 2**size.bit_length()
            self.dat = [default]*(self.size*2)
            self.op = op

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

        def add(self, i, x):
            i += self.size
            self.dat[i] = self.op(self.dat[i], x)
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i], x)

        def get(self, a, b = None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            res = None
            while l < r:
                if l & 1:
                    if res is None:
                        res = self.dat[l]
                    else:
                        res = self.op(res, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    if res is None:
                        res = self.dat[r]
                    else:
                        res = self.op(res, self.dat[r])
                l >>= 1
                r >>= 1
            return res

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

    w,h,n = LI()
    p = []
    lx = set()
    ly = set()
    for i in range(n):
        x,y,s,t = LI()
        if check(x,y)&check(s,t):
            p.append((x,y,s,t))
            lx |= {x,s}
            ly |= {y,t}
    if len(p) < 2:
        print("YES")
        return
    lx = list(lx)
    ly = list(ly)
    lx.sort()
    ly.sort()
    px = {lx[i]: i for i in range(len(lx))}
    py = {ly[i]: i for i in range(len(ly))}
    w,h = max(px.values()),max(py.values())
    fy0 = SegmentTree(w+1, 0)
    fyh = SegmentTree(w+1, 0)
    fx0 = SegmentTree(h+1, 0)
    fxw = SegmentTree(h+1, 0)
    for i in range(len(p)):
        b = 1<<i
        x,y,s,t = p[i]
        x,y,s,t = px[x],py[y],px[s],py[t]
        if x == 0:
            f1 = fx0.get(0,y+1)
        elif x == w:
            f1 = fxw.get(0,y+1)
        elif y == 0:
            f1 = fy0.get(0,x+1)
        else:
            f1 = fyh.get(0,x+1)
        if s == 0:
            f2 = fx0.get(0,t+1)
        elif s == w:
            f2 = fxw.get(0,t+1)
        elif t == 0:
            f2 = fy0.get(0,s+1)
        else:
            f2 = fyh.get(0,s+1)
        if f1^f2:
            print("NO")
            return
        if x == 0:
            if s == 0:
                y,t = min(y,t),max(y,t)
                fx0.add(y,b)
                fx0.add(t+1,-b)
            elif s == w:
                fx0.add(0,b)
                fx0.add(y+1,-b)
                fy0.add(0,b)
                fxw.add(0,b)
                fxw.add(t+1,-b)
            elif t == 0:
                fx0.add(0,b)
                fx0.add(y+1,-b)
                fy0.add(0,b)
                fy0.add(s+1,-b)
            else:
                fx0.add(y,b)
                fyh.add(0,b)
                fyh.add(s+1,-b)
        elif x == w:
            if s == 0:
                fx0.add(0,b)
                fx0.add(t+1,-b)
                fy0.add(0,b)
                fxw.add(0,b)
                fxw.add(y+1,-b)
            elif s == w:
                y,t = min(y,t),max(y,t)
                fxw.add(y,b)
                fxw.add(t+1,-b)
            elif t == 0:
                fy0.add(s,b)
                fxw.add(0,b)
                fxw.add(y+1,-b)
            else:
                fxw.add(y,b)
                fyh.add(s,b)
        elif y == 0:
            if s == 0:
                fy0.add(0,b)
                fy0.add(x+1,-b)
                fx0.add(0,b)
                fx0.add(t+1,-b)
            elif s == w:
                fy0.add(x,b)
                fxw.add(0,b)
                fxw.add(t+1,-b)
            elif t == 0:
                x,s = min(x,s),max(x,s)
                fy0.add(x,b)
                fy0.add(s,-b)
            else:
                fy0.add(x,b)
                fxw.add(0,b)
                fyh.add(s,b)
        else:
            if s == 0:
                fx0.add(t,b)
                fyh.add(0,b)
                fyh.add(x+1,-b)
            elif s == w:
                fxw.add(t,b)
                fyh.add(x,b)
            elif t == 0:
                fyh.add(x,b)
                fxw.add(0,b)
                fy0.add(s,b)
            else:
                x,s = min(x,s),max(x,s)
                fyh.add(x,b)
                fyh.add(s,-b)
    print("YES")
    return

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
R, C, N = map(int, input().split())


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def check(x, y):
    if x == 0:
        return y
    elif x == R:
        return R + C + C - y
    elif y == 0:
        return C + R + C + R - x
    elif y == C:
        return C + x
    else:
        return -1


lr_list = []
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    z1, z2 = check(x1, y1), check(x2, y2)
    if z1 >= 0 and z2 >= 0:
        lr_list.append((min(z1, z2) + 1, max(z1, z2) + 1))

bit = Bit(2*(R+C) + 3)
for l, r in lr_list:
    if (bit.sum(r) - bit.sum(l)) % 2 == 1:
        print('NO')
        exit()
    bit.add(l, 1)
    bit.add(r, 1)

print('YES')

Submission status: Time Limit Exceeded

Solution code:
r,c,n = map(int,input().split())
a = [list(map(int, input().split())) for _ in range(n)]
iru = []
for i in range(n):
  if ((a[i][0] == 0 or a[i][0] == r or a[i][1] == 0 or a[i][1] == c) and (a[i][2] == 0 or a[i][2] == r or a[i][3] == 0 or a[i][3] == c)):
    iru.append(a[i])
if len(iru) <= 1:
  print("YES")
else:
  for i in range(len(iru)):
    b = iru[i]
    b1 = [b[0],b[1]]
    b2 = [b[2],b[3]]
    if b1[0] == 0:
      b1 = b1[1]
    elif b1[1] == c:
      b1 = b1[0] + b1[1]
    elif b1[0] == r:
      b1 = c*2 +r-1 -b1[1]
    else:
      b1 = c*2 + r*2 -2 - b1[0]
      
    if b2[0] == 0:
      b2 = b2[1]
    elif b2[1] == c:
      b2 = b2[0] + b2[1]
    elif b2[0] == r:
      b2 = c*2 +r-1 -b2[1]
    else:
      b2 = c*2 + r*2 -2 - b2[0]
    if b1 > b2:
      tmp = b1 +0
      b1 = b2 +0
      b2 = tmp + 0
    for j in range(i+1,len(iru)):
      d = iru[j]
      d1 = [d[0],d[1]]
      d2 = [d[2],d[3]]
      if d2[0] == 0:
        d2 = d2[1]
      elif d2[1] == c:
        d2 = d2[0] + d2[1]
      elif d2[0] == r:
        d2 = c*2 +r-1 -d2[1]
      else:
        d2 = c*2 + r*2 -2 - d2[0]
      
      if d1[0] == 0:
        d1 = d1[1]
      elif d1[1] == c:
        d1 = d1[0] + d1[1]
      elif d1[0] == r:
        d1 =  c*2 +r-1 -d1[1]
      else:
        d1 = c*2 + r*2 -2 - d1[0]
      if d1 > d2:
        tmp = d1 +0
        d1 = d2 +0
        d2 = tmp + 0
      if (b1 <= d1 and d1 <= b2 and b2 <= d2):
        print("NO")
        exit()
      elif (d1 <= b1 and b1 <= d2 and d2 <= b2):
        print("NO")
        exit()
  print("YES")

Submission status: Time Limit Exceeded

Solution code:
R, C, N = map(int, input().split())
def calc(x, y):
    if x == 0 or y == C:
        return x + y
    return 2*R + 2*C - x - y
A = [None]*(2*R + 2*C)
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if not ((x1 in [0, R] or y1 in [0, C]) and (x2 in [0, R] or y2 in [0, C])):
        continue
    A[calc(x1, y1)] = i
    A[calc(x2, y2)] = i

st = []
for a in A:
    if st and st[-1] == a:
        st.pop()
    elif a is not None:
        st.append(a)
print('YES' if not st else 'NO')

Submission status: Time Limit Exceeded

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

vec = []

l = []
b = []
r = []
t = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    if x == 0:
        l.append([x, y, i])
    elif y == 0:
        t.append([x, y, i])
    elif x == w:
        r.append([x, y, i])
    elif y == h:
        b.append([x, y, i])
    if x1 == 0:
        l.append([x1, y1, i])
    elif y1 == 0:
        t.append([x1, y1, i])
    elif x1 == w:
        r.append([x1, y1, i])
    elif y1 == h:
        b.append([x1, y1, i])

sorted_node = (
          sorted(l, key=lambda x: x[1])
        + sorted(b, key=lambda x: x[0])
        + sorted(r, key=lambda x: x[1], reverse=True)
        + sorted(t, key=lambda x: x[0], reverse=True)
        )

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

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

Submission status: Time Limit Exceeded

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

vec = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    vec.append([x, y, i])
    vec.append([x1, y1, i])

sorted_node = []

vec.sort(key=lambda x: x[1])
for p in vec:
    if p[0] == 0:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[0])
for p in vec:
    if p[1] == h:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[1], reverse=True)
for p in vec:
    if p[0] == w:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

vec.sort(key=lambda x: x[0], reverse=True)
for p in vec:
    if p[1] == 0:
        p[0] = -1
        p[1] = -1
        sorted_node.append(p)

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

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

Submission status: Time Limit Exceeded

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

vec = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    vec.append((x, y, i))
    vec.append((x1, y1, i))

sorted_node = []

vec.sort(key=lambda x: x[1])
for p in vec:
    if p[0] == 0:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[0])
for p in vec:
    if p[1] == h:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[1], reverse=True)
for p in vec:
    if p[0] == w:
        sorted_node.append(p)
        vec.remove(p)

vec.sort(key=lambda x: x[0], reverse=True)
for p in vec:
    if p[1] == 0:
        sorted_node.append(p)
        vec.remove(p)

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

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

Submission status: Time Limit Exceeded

Solution code:
R, C, N = map(int, raw_input().split())
 
bad = False
left = []
right = []
length = R*2 + C*2
for i in range(N):
	if bad:
		x = raw_input()
		continue
	else:
		x, y, xx, yy = map(int, raw_input().split())
	if (x in [0, R] or y in [0, C]) and (xx in [0, R] or yy in [0, C]):
		if x == 0 or y == C:
			first = x+y
		else:
			first = length-(x+y)
		if xx == 0 or yy == C:
			second = xx+yy
		else:
			second = length-(xx+yy)
		new_left, new_right = (second, first) if first < second else (first, second)
		left_count, right_count = 0, 0
		for i in range(len(left))[::]:
			if new_left < left[i]:
				break
			left_count += 1
		left.insert(left_count, new_left)
		for i in range(len(left))[::]:
			if new_right < left[i]:
				break
			left_count -= 1
		for i in range(len(right))[::]:
			if right[i] < new_right:
				break
			right_count += 1
		right.insert(right_count, new_right)
		for i in range(len(right))[::]:
			if right[i] < new_left:
				break
			right_count -= 1
 
		if left_count != right_count:
			bad = True
 
 
if bad:
	print 'NO'
else:
	print 'YES'

Submission status: Time Limit Exceeded

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

bad = False
left = 0
right = 0
length = R*2 + C*2
for i in range(N):
	if bad:
		x = raw_input()
		continue
	else:
		x, y, xx, yy = map(int, raw_input().split())
	if (x in [0, R] or y in [0, C]) and (xx in [0, R] or yy in [0, C]):
		if x == 0 or y == C:
			first = x+y
		else:
			first = length-(x+y)
		if xx == 0 or yy == C:
			second = xx+yy
		else:
			second = length-(xx+yy)
		new_left, new_right = ((1 << second), (1 << first)) if first < second else ((1 << first), (1 << second))
		new_line = new_left - new_right
		if bin(new_line & left).count('1') == bin(new_line & right).count('1'):
			left += new_left
			right += new_right
		else:
			bad = True

		# R:2 C:4 2*2 + 4*2 = 12 0 1 2 3 4 5 6 7 8 9 10 11 12

if bad:
	print 'NO'
else:
	print 'YES'

Submission status: Time Limit Exceeded

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

bad = False
left = 0
right = 0
for i in range(N):
	if bad:
		x = raw_input()
		continue
	else:
		x, y, xx, yy = map(int, raw_input().split())
	if (x in [0, R] or y in [0, C]) and (xx in [0, R] or yy in [0, C]):
		if x == 0 or y == C:
			first = x+y
		else:
			first = (R*2 + C*2)-(x+y)
		if xx == 0 or yy == C:
			second = xx+yy
		else:
			second = (R*2 + C*2)-(xx+yy)
		new_left, new_right = ((1 << second), (1 << first)) if first < second else ((1 << first), (1 << second))
		new_line = new_left - new_right
		if bin(new_line & left).count('1') == bin(new_line & right).count('1'):
			left |= new_left
			right |= new_right
		else:
			bad = True

		# R:2 C:4 2*2 + 4*2 = 12 0 1 2 3 4 5 6 7 8 9 10 11 12

if bad:
	print 'NO'
else:
	print 'YES'

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()



def main():
    R,C,N = LI()
    a = []
    def ff(x,y):
        if x == 0:
            return (0,y)
        if x == R:
            return (R,-y)
        if y == 0:
            return (R+1, -x)
        return (1, x)

    for _ in range(N):
        x1,y1,x2,y2 = LI()
        if (0 < x1 < R and 0 < y1 < C) or (0 < x2 < R and 0 < y2 < C):
            continue
        a.append((ff(x1,y1),_))
        a.append((ff(x2,y2),_))
    a.sort()
    b = [a[i][1] for i in range(len(a))]
    s = []
    for c in b:
        if not s:
            s.append(c)
            continue
        if c == s[-1]:
            s = s[:-1]
        else:
            s.append(c)

    if len(s) > 2:
        return 'NO'
    return 'YES'

print(main())

Submission status: Time Limit Exceeded

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))


R, C, N = rli()
lis = []
idx = 0
i = 0
for j in range(N):
    x1, y1, x2, y2 = rli()
    if((x1 % R == 0 or y1 % C == 0) and (x2 % R == 0 or y2 % C == 0)):
        i += 1
        for _ in range(2):
            if(y1 == 0):
                lis.append([x1, i])
            elif(x1 == R):
                lis.append([R+y1, i])
            elif(y1 == C):
                lis.append([2*R+C-x1, i])
            elif(x1 == 0):
                lis.append([2*R+2*C-y1, i])
            x1 = x2
            y1 = y2
lis.sort()
stack = []
ans = True
for k in range(2*i):
    if(lis[k][1] in stack):
        if(lis[k][1] != stack.pop()):
            ans = False
            break
    else:
        stack.append(lis[k][1])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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