Submission #61192725

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
"""import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10**7)"""
import bisect
n,m=map(int,input().split())
bx={}
by={}
wx={}
wy={}
for _ in range(m):
    x,y,c=sys.stdin.readline().split()
    x,y=int(x),int(y)
    if c=="B":
        if x in bx:
            bx[x]=max(bx[x],y)
        else:
            bx[x]=y
        if y in by:
            by[y]=max(by[y],x)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
"""import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10**7)"""
import bisect

n,m=map(int,input().split())
bx={}
by={}
wx={}
wy={}
for _ in range(m):
    x,y,c=sys.stdin.readline().split()
    x,y=int(x),int(y)
    if c=="B":
        if x in bx:
            bx[x]=max(bx[x],y)
        else:
            bx[x]=y
        if y in by:
            by[y]=max(by[y],x)
        else:
            by[y]=x
    if c=="W":
        if x in wx:
            wx[x]=min(wx[x],y)
        else:
            wx[x]=y
        if y in wy:
            wy[y]=min(wy[y],x)
        else:
            wy[y]=x
if len(bx)==0 or len(wx)==0:
    print("Yes")
    exit()

bx_l=[]
by_l=[]
for i in bx:
    bx_l.append([i,bx[i]])
for i in by:
    by_l.append([i,by[i]])
bx_l.sort()
by_l.sort()
bx_len=len(bx_l)
by_len=len(by_l)
bx_x=[0]*bx_len
bx_v=[0]*bx_len
by_y=[0]*by_len
by_v=[0]*by_len

cur=0
for i in range(bx_len):
    cur=max(cur,bx_l[-i-1][1])
    bx_v[-i-1]=cur
    bx_x[-i-1]=bx_l[-i-1][0]
cur=0
for i in range(by_len):
    cur=max(cur,by_l[-i-1][1])
    by_v[-i-1]=cur
    by_y[-i-1]=by_l[-i-1][0]

"""
def bs_x(x):
    l=0
    r=bx_len-1
    if x<=bx_l[0][0]:
        return bx_l[0][1]
    if x>bx_l[r][0]:
        return 0
    while l<r-1:
        mid=(l+r)//2
        if x==bx_l[mid][0]:
            return bx_l[mid][1]
        elif x<bx_l[mid][0]:
            r=mid
        else:
            l=mid
    return bx_l[r][1]

def bs_y(y):
    l=0
    r=by_len-1
    if y<=by_l[0][0]:
        return by_l[0][1]
    if y>by_l[r][0]:
        return 0
    while l<r-1:
        mid=(l+r)//2
        if y==by_l[mid][0]:
            return by_l[mid][1]
        elif y<by_l[mid][0]:
            r=mid
        else:
            l=mid
    return by_l[r][1]
"""

for i in wx:
    v=bisect.bisect_left(bx_x,i)
    if v<bx_len and wx[i]<=bx_v[v]:
        print("No")
        exit()
for j in wy:
    v=bisect.bisect_left(by_y,j)
    if v<by_len and wy[j]<=by_v[v]:
        print("No")
        exit()
print("Yes")

Submission Info

Judge Result