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:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    R, C, N = ILI()
    num_point = []
    for __ in range(N):
        x_1, y_1, x_2, y_2 = ILI()
        num_point.append([(x_1, y_1), (x_2, y_2)])
    return R, C, N, num_point


# 周上を (0, 0) を原点として反時計回りに 1 本の数直線とした時の point の座標を返す．
# 周上にあるかの判定も行う．
def change_edge_point(R, C, point):
    x, y = point
    if x == 0:
        return R * 2 + C + (C - y)
    if x == R:
        return R + y
    if y == 0:
        return x
    if y == C:
        return R + C + (R - x)


def solve(R, C, N, num_point):
    point_double = []
    for ind, point in enumerate(num_point):
        p_1, p_2 = point
        if ((p_1[0] == 0 or p_1[0] == R) or (p_1[1] == 0 or p_1[1] == C)) and ((p_2[0] == 0 or p_2[0] == R) or (p_2[1] == 0 or p_2[1] == C)):
            point_double.append((ind + 1, change_edge_point(R, C, p_1)))
            point_double.append((ind + 1, change_edge_point(R, C, p_2)))
    point_double.sort(key=lambda  x: x[1])
    stack = []
    for point in point_double:
        if len(stack) == 0:
            stack.append(point[0])
            continue
        if point[0] == stack[-1]:
            stack.pop()
        else:
            stack.append(point[0])
    
    if len(stack) == 0:
        return "YES"
    else:
        return "NO"
    

def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

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
stack=[]
for i in xrange(len(urdl)):
    if len(stack)==0:
        stack.append(urdl[i][1])
    elif stack[-1]==urdl[i][1]:
        stack.pop()
    else:
        stack.append(urdl[i][1])
print "YES" if len(stack)==0 else "NO"

Submission status: Accepted

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 = []
exist = [False for _ in range(2*i)]
ans = True
for k in range(2*i):
    if(exist[lis[k][1]]):
        if(lis[k][1] != stack.pop()):
            ans = False
            break
        exist[lis[k][1]] = False
    else:
        stack.append(lis[k][1])
        exist[lis[k][1]] = True
if(ans):
    print("YES")
else:
    print("NO")

Submission status: Accepted

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: Accepted

Solution code:
# coding: utf-8

import heapq


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


def on_edge(x1, y1, x2, y2, R, C, i, edge_points):
    c1 = coord_on_edge(x1, y1, R, C)
    c2 = coord_on_edge(x2, y2, R, C)
    if c1 is not None and c2 is not None:
        heapq.heappush(edge_points, (c1, i))
        heapq.heappush(edge_points, (c2, i))


def solve():
    R, C, N = map(int, input().split())
    edge_points = []            # (coord, point#)
    for i in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        on_edge(x1, y1, x2, y2, R, C, i, edge_points)
    q = []
    while edge_points:
        c, i = heapq.heappop(edge_points)
        # print((c, i))           # dbg
        if len(q) and q[-1] == i:
            q.pop()
        else:
            q.append(i)
    if len(q):
        return "NO"
    return "YES"


print(solve())

Submission status: Accepted

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

points = []

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

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)):
        points.append((i + 1, dist(x1, y1)))
        points.append((i + 1, dist(x2, y2)))
points.sort(key=lambda p: p[1])
l = []
for point in points:
    if len(l) == 0:
        l.append(point[0])
        continue
    if point[0] == l[-1]:
        l.pop()
    else:
        l.append(point[0])
if len(l) == 0:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

# sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def pos(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, = read_int_list()
x = [0, 0]
y = [0, 0]
a = []
for i in range(n):
    x[0], y[0], x[1], y[1] = read_int_list()
    if (x[0] in [0, r] or y[0] in [0, c]) and (x[1] in [0, r] or y[1] in [0, c]):
        for k in range(2):
            a.append((pos(x[k], y[k]), i))
m = len(a) // 2
a.sort()

res = 'YES'
started = set()
s = []
for p, i in a:
    if i not in started:
        started.add(i)
        s.append(i)
    else:
        if s[-1] != i:
            res = 'NO'
            break
        s.pop()

print(res)

Submission status: Accepted

Solution code:
def calc_pos(x, y, R, C):
    if y == 0:
        return x
    if y == C:
        return 2 * R + C - x
    if x == R:
        return R + y
    if x == 0:
        return 2 * R + 2 * C - y

def read_data():
    R, C, N = map(int, input().split())
    pairs = []
    xys = []
    idx = 0
    for i in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        xys.append((x1, y1))
        xys.append((x2, y2))
        if (x1 != 0 and x1 != R and y1 != 0 and y1 != C) or (x2 != 0 and x2 != R and y2 != 0 and y2 != C):
            continue
        a = calc_pos(x1, y1, R, C)
        b = calc_pos(x2, y2, R, C)
        pairs.append((a, idx))
        pairs.append((b, idx))
        idx += 1
    pairs.sort()
    return pairs, xys

def is_valid(xys):
    xys.sort()
    prev_x, prev_y = xys[0]
    for x, y in xys[1:]:
        if prev_x == x and prev_y == y:
            return False
        prev_x = x
        prev_y = y
    return True

def solve(pairs, xys):
    if len(xys) == 2:
        return "YES"
    if not is_valid(xys):
        return "NO"    
    idxs = [i for a, i in pairs]
    stack = []
    for idx in idxs:
        if stack and stack[-1] == idx:
            stack.pop()
            continue
        stack.append(idx)
    if stack:
        return "NO"
    else:
        return "YES"

pairs, xys = read_data()
print(solve(pairs, xys))

Submission status: Runtime Error

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 = [l[0][1]]
for x, i in l[1:]:
    s.append(0)
    s.append(i)
r = [0] * len(s)
i, j = 0, 0
while i < len(s):
    while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
        j += 1
    r[i] = j
    k = 1
    while i - k >= 0 and k + r[i - k] < j:
        r[i + k] = r[i - k]
        k += 1
    i += k
    j -= k
for i in range(1, len(s), 2):
    p = r[i]
    if i == p - 1:
        m = (len(s) - p * 2) // 2
        if m == -1 or (m > 0 and r[-m] == m):
            print('YES')
            exit(1)
print('NO')

Submission status: Runtime Error

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)):
        max_ = max(max_, *array[i])
        array[i][0] = memo[array[i][0]]
        array[i][1] = memo[array[i][1]]
    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.random()
    bit.add(begin, end, tmp)
print("YES")

Submission status: Runtime Error

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)

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))
        
bit = BIT(r+r+c+c)  
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.random()
    bit.add(begin, end, tmp)
print("YES")

Submission status: Runtime Error

Solution code:
import random


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)

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))
        
bit = BIT(r+r+c+c)  
for i in range(len(query)):
    begin, end = query[i]
    if bit.get_val(begin) != bit.get_val(end - 1):
        print("NO")
        exit()
    bit.add(begin, end, random.random())
print("YES")

Submission status: Runtime Error

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_raw = []
z_list = []
for i 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_raw.append((min(z1, z2), max(z1, z2)))
        z_list.append(z1)
        z_list.append(z2)

z_list.sort()
idx = {zi: i+1 for i, zi in enumerate(z_list)}
lr_list = []
for l_raw, r_raw in lr_list_raw:
    lr_list.append((idx[l_raw], idx[r_raw]))

bit = Bit(len(lr_list) + 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: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    R,C,N = map(int,input().split())
    P = []
    X = {0,R}
    Y = {0,C}
    M = 0
    for i in range(N):
        x1,y1,x2,y2 = map(int,input().split())
        if (x1 in X or y1 in Y) and  (x2 in X or y2 in Y):
            if y1==0:
                L1 = x1
            elif x1==R:
                L1 = R+y1
            elif y1==C:
                L1 = 2*R + C - x1
            else:
                L1 = 2*(R+C) - y1
            
            if y2==0:
                L2 = x2
            elif x2==R:
                L2 = R+y2
            elif y2==C:
                L2 = 2*R + C - x2
            else:
                L2 = 2*(R+C) - y2
                
            P.append([min(L1,L2), max(L1,L2)])
    print("AAA")
    P = sorted(P, key = lambda a:a[0])
    M = len(P)
    
    flag = 0
    Q = []
    for i in range(M):
        x1,x2 = P[i]
        if Q == []:
            Q.append([x1,x2])
        else:
            while Q[-1][1] < x1 and Q!=[]:
                Q.pop()
            if Q==[]:
                Q.append([x1,x2])
            else:
                y1,y2 = Q[-1]
                if y2 < x2:
                    flag = 1
                    break
                else:
                    Q.append([x1,x2])
    if flag == 1:
        print("NO")
    else:
        print("YES")
    
main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    R,C,N = map(int,input().split())
    P = []
    X = {0,R}
    Y = {0,C}
    M = 0
    for i in range(N):
        x1,y1,x2,y2 = map(int,input().split())
        if (x1 in X or y1 in Y) and  (x2 in X or y2 in Y):
            if y1==0:
                L1 = x1
            elif x1==R:
                L1 = R+y1
            elif y1==C:
                L1 = 2*R + C - x1
            else:
                L1 = 2*(R+C) - y1
            
            if y2==0:
                L2 = x2
            elif x2==R:
                L2 = R+y2
            elif y2==C:
                L2 = 2*R + C - x2
            else:
                L2 = 2*(R+C) - y2
                
            P.append([min(L1,L2), max(L1,L2)])
    P = sorted(P, key = lambda a:a[0])
    M = len(P)
    print("AAA")
    
    flag = 0
    Q = []
    for i in range(M):
        x1,x2 = P[i]
        if Q == []:
            Q.append([x1,x2])
        else:
            while Q[-1][1] < x1 and Q!=[]:
                Q.pop()
            if Q==[]:
                Q.append([x1,x2])
            else:
                y1,y2 = Q[-1]
                if y2 < x2:
                    flag = 1
                    break
                else:
                    Q.append([x1,x2])
    if flag == 1:
        print("NO")
    else:
        print("YES")
    
main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    R,C,N = map(int,input().split())
    P = []
    X = {0,R}
    Y = {0,C}
    M = 0
    for i in range(N):
        x1,y1,x2,y2 = map(int,input().split())
        if (x1 in X or y1 in Y) and  (x2 in X or y2 in Y):
            if y1==0:
                L1 = x1
            elif x1==R:
                L1 = R+y1
            elif y1==C:
                L1 = 2*R + C - x1
            else:
                L1 = 2*(R+C) - y1
            
            if y2==0:
                L2 = x2
            elif x2==R:
                L2 = R+y2
            elif y2==C:
                L2 = 2*R + C - x2
            else:
                L2 = 2*(R+C) - y2
                
            P.append([min(L1,L2), max(L1,L2)])
    P = sorted(P, key = lambda a:a[0])
    M = len(P)
    
    flag = 0
    Q = []
    for i in range(M):
        x1,x2 = P[i]
        if Q == []:
            Q.append([x1,x2])
        else:
            while Q[-1][1] < x1 and Q!=[]:
                Q.pop()
            if Q==[]:
                Q.append([x1,x2])
            else:
                y1,y2 = Q[-1]
                if y2 < x2:
                    flag = 1
                    break
                else:
                    Q.append([x1,x2])
    if flag == 1:
        print("NO")
    else:
        print("YES")
    
main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    R,C,N = map(int,input().split())
    P = []
    X = {0,R}
    Y = {0,C}
    M = 0
    for i in range(N):
        x1,y1,x2,y2 = map(int,input().split())
        if (x1 in X or y1 in Y) and  (x2 in X or y2 in Y):
            M += 1
            if y1==0:
                L1 = x1
            elif x1==R:
                L1 = R+y1
            elif y1==C:
                L1 = 2*R + C - x1
            else:
                L1 = 2*(R+C) - y1
            
            if y2==0:
                L2 = x2
            elif x2==R:
                L2 = R+y2
            elif y2==C:
                L2 = 2*R + C - x2
            else:
                L2 = 2*(R+C) - y2
                
            P.append([min(L1,L2), max(L1,L2)])
    P = sorted(P, key = lambda a:a[0])
    from collections import deque
    
    flag = 0
    Q = []
    for i in range(M):
        x1,x2 = P[i]
        if Q == []:
            Q.append([x1,x2])
        else:
            while Q[-1][1] < x1 and Q!=[]:
                Q.pop()
            if Q==[]:
                Q.append([x1,x2])
            else:
                y1,y2 = Q[-1]
                if y2 < x2:
                    flag = 1
                    break
                else:
                    Q.append([x1,x2])
    if flag == 1:
        print("NO")
    else:
        print("YES")
    
main()

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T, class U>using vp = vector<pair<T, U>>;
template<class T>using vv = vector<vector<T>>; template<class T, class U>using vvp = vv<pair<T, U>>;
template<class T>vv<T> vvec(size_t n, size_t m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 28, MAX = 1e5 + 5, MOD = 1e9 + 7;
constexpr ll LINF = 1ll << 60; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int R, C, N;
vi X1, X2, Y1, Y2;

int main() {
    cin >> R >> C >> N;
    X1.resize(N);
    X2.resize(N);
    Y1.resize(N);
    Y2.resize(N);
    rep(i, N) {
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
    }

    // 両端が辺に乗ってるもののみ
    // 左上0反時計回りに座標振る
    vp<int, int> sepa;
    rep(i, N) {
        if ((X1[i] % C && Y1[i] % R) || (X2[i] % C && Y2[i] % R)) continue;

        int crd1 = Y1[i] == 0 ? X1[i] :
            (X1[i] == C ? C + Y1[i] :
            (Y1[i] == R ? R + C + C - X1[i] :
                R + 2 * C + R - Y1[i]));
        int crd2 = Y2[i] == 0 ? X2[i] :
            (X2[i] == C ? C + Y2[i] :
            (Y2[i] == R ? R + C + C - X2[i] :
                R + 2 * C + R - Y2[i]));
        if (crd1 > crd2) swap(crd1, crd2);

        sepa.emplace_back(crd1, crd2);
    }
    sort(all(sepa));

    bool ans = true;
    if (!sepa.empty()) {
        int i = 0;
        while (i < sepa.size()) {
            int border = sepa[i].second;
            int j = i + 1;
            for (; j < sepa.size(); ++j) {
                if (sepa[j].first > border) break;
                else if (sepa[j].second > sepa[j - 1].second) {
                    ans = false;
                }
            }
            i = j;
        }
    }

    write(ans ? "YES" : "NO");
}

Submission status: Runtime Error

Solution code:
import math
n,m = list(map(int, input().split()))
n, m = max(n,m), min(n, m)

if n - m > 1:
    ans = 0
elif n - m == 1:
    k = math.factorial(m) % (10**9 + 7)
    ans = k*k*n % (10**9 + 7)
else:
    k = math.factorial(m) % (10**9 + 7)
    ans = k*k*2 % (10**9 + 7)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

R,C,N = [int(i) for i in input().split()]
lec = [[0] * (C+1) for i in range(R+1)]

x1 = [0]*N
x2 = [0]*N
y1 = [0]*N
y2 = [0]*N
ngx1 = []
ngx2 = []
ngy1 = []
ngy2 = []

for i in range(0,N):
    x1[i], y1[i], x2[i], y2[i] = [int(i) for i in input().split()]

for i in range(0,N):
    if (x1[i] in [0,R] or y1[i] in [0,C]) and (x2[i] in [0,R] or y2[i] in [0,C]):
        ngx1.append(x1[i])
        ngx2.append(x2[i])
        ngy1.append(y1[i])
        ngy2.append(y2[i])

if len(ngx1) in [0,1]:
    print('YES')
    sys.exit()
else:
    for j in range(1,len(ngx1)):
        for i in range(j,len(ngx1)):
            tc=(ngx1[0]-ngx2[0])*(ngy1[i]-ngy1[0])+(ngy1[0]-ngy2[0])*(ngx1[0]-ngx1[i])
            td=(ngx1[0]-ngx2[0])*(ngy2[i]-ngy1[0])+(ngy1[0]-ngy2[0])*(ngx1[0]-ngx2[i])
            if tc*td<0:
                print('NO')
                sys.exit()
print('YES')

Submission status: Runtime Error

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

false_flag = False
lines = []
for i in range(N):
	if false_flag:
		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_line = [first, second] if first < second else [second, first]
		j = 0
		for j in range(len(lines)):
			new_left = new_line[0]
			last_left = lines[j][0]
			if new_left < last_left:
				new_right = new_line[1]
				last_right = lines[j][1]
				if last_left < new_right and new_right < last_right:
					false_flag = True
				else:
					lines.insert(j, new_line)
				break
		else:
			lines.append(new_line)

scopes = []
scopes.append(lines.pop(0))
while lines and not false_flag:
	while scopes:
		next_scope = lines.pop(0)
		right = scopes[-1][1]
		next_left = next_scope[0]
		next_right = next_scope[1]
		if next_left < right:
			if next_right < right:
				if lines:
					scopes.append(next_scope)
				else:
					break
			else:
				false_flag = True
				break
		else:
			scopes.pop()
	else:
		scopes.append(next_scope)

if false_flag:
	print 'NO'
else:
	print 'YES'

Submission status: Runtime Error

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

line = [-1 for _ in range(R*2 + C*2)]
for i in range(N):
	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]):
		line_pos = 0
		if x <= y:
			line_pos = x+y
		else:
			line_pos = (R*2 + C*2)-(x+y)
		line[line_pos] = i
		if xx <= yy:
			line_pos = xx+yy
		else:
			line_pos = (R*2 + C*2)-(xx+yy)
		line[line_pos] = i
queue = ''
for i in range(len(line)):
	key = str(line[i])
	if key != '-1':
		if key in queue:
			if key == queue[-1:]:
				queue = queue[:-1]
			else:
				break
		else:
			queue += key
if queue:
	print 'NO'
else:
	print 'YES'

Submission status: Runtime Error

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

line = [-1 for _ in range(R*2 + C*2)]
for i in range(N):
	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]):
		line_pos = 0
		if x <= y:
			line_pos = x+y
		else:
			line_pos = (R*2 + C*2)-(x+y)
		line[line_pos] = i
		if xx <= yy:
			line_pos = xx+yy
		else:
			line_pos = (R*2 + C*2)-(xx+yy)
		line[line_pos] = i
queue = []
for i in range(len(line)):
	key = line[i]
	if key != -1:
		if key in queue:
			if key == queue[len(queue)-1]:
				queue.pop()
			else:
				break
		else:
			queue.append(key)
if queue:
	print 'NO'
else:
	print 'YES'

Submission status: Runtime Error

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    R, C, N = ILI()
    num_point = []
    for __ in range(N):
        x_1, y_1, x_2, y_2 = ILI()
        num_point.append([(x_1, y_1), (x_2, y_2)])
    return R, C, N, num_point


# 周上を (0, 0) を原点として反時計回りに 1 本の数直線とした時の point の座標を返す．
# 周上にあるかの判定も行う．
def change_edge_point(R, C, point):
    x, y = point
    if 0 < x < C or 0 < y < R:
        return False
    if y == 0:
        return x
    elif y == R:
        return C + R + C - x
    if x == 0:
        return C + y
    elif x == R:
        return C + R + C + R - y


def solve(R, C, N, num_point):
    point_double = []
    for point in num_point:
        p_1, p_2 = point
        ret_1 = change_edge_point(R, C, p_1)
        ret_2 = change_edge_point(R, C, p_2)
        if ret_1 is False or ret_2 is False:
            continue
        point_double.append((min(ret_1, ret_2), max(ret_1, ret_2)))åç

    for p_1, p_2 in itertools.combinations(point_double, 2):
        if p_1[0] == p_2[0] or p_1[1] == p_2[1]:
            return "NO"

        if p_1[0] < p_2[0]:
            if p_1[1] > p_2[1]:
                continue
            else:
                return "NO"
        elif p_1[0] > p_2[0]:
            if p_1[1] < p_2[1]:
                continue
            else:
                return "NO"

    return "YES"


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()