Problem:


問題 A : Koto Distance

問題文

	Koto は言わずと知れた碁盤の目の街である．
	この街は東西方向に W メートル，南北方向に H メートルに伸びる長方形の領域によってできている．
	この街の西端から x メートル，南端から y メートルの点は (x,&thinsp; y)  と記される．
	ここの街に住む人は古くから伝わる独自の文化を重んじており，その一つにKoto距離という変わった距離尺度がある．
2つの点 (x_1, y_1)，(x_2, y_2) の Koto 距離は，min(|x_1 - x_2|,&thinsp; |y_1 - y_2|) によって定義される．

	最近この街全体に Wifi を使えるようにする計画が立ち上がった．
	現在の計画では，親機を N 個作ることになっている．
i 番目の親機は点 (x_i, &thinsp;y_i) に設置され，Koto距離が w_i 以下の領域に対して Wifi を提供する．

	親機を計画どおり建てた場合に，街の内部及び境界上に Wifi を提供できるかどうかを判定せよ．

	なお，Koto距離は一般に三角不等式を満たさないため，距離の公理を満たさないということはここだけの秘密である．

入力形式

入力は以下の形式で与えられる．

N W H
x_1 y_1 w_1
...
x_N y_N w_N

出力形式

街の内部および境界上に Wifi を提供できるなら “Yes” を，そうでない場合は “No” を出力せよ．

制約

1 ≤ N ≤ 10^5

1 ≤ W ≤ 10^5

1 ≤ H ≤ 10^5

0 ≤ x_i ≤ W

0 ≤ y_i ≤ H

1 ≤ w_i ≤ 10^5

同一座標に親機は複数存在しない

入出力例

入力例 1

3 9 9
2 2 2
5 5 2
8 8 2

出力例 1

Yes

２番目の親機が提供するWifiの範囲は以下の通りである．

入力例 2

2 7 7
2 2 1
6 6 1

出力例 2

No

入力例 3

3 10 20
5 10 5
2 10 1
8 10 1

出力例 3

Yes



Sample input:
3 9 9
2 2 2
5 5 2
8 8 2


Sample output:
Yes

Submission status: Accepted

Solution code:
def read():
  return list(map(int,input().split()))

def ok(width,xs,ws):
  x=0
  for l,r in sorted((x-w,x+w) for x,w in zip(xs,ws)):
    if x<l: return False
    x=max(x,r)
  return width<=x

while 1:
  try:
    n,w,h=read()
    xs,ys,ws=([0]*n for _ in range(3))
    for i in range(n):
      xs[i],ys[i],ws[i]=read()
  except: break
  print("Yes" if ok(w,xs,ws) or ok(h,ys,ws) else "No")

Submission status: Accepted

Solution code:
N,W,H = map(int,raw_input().split())
X,Y = [0]*(W+1),[0]*(H+1)
for loop in xrange(N):
    x,y,w = map(int,raw_input().split())
    X[max(0,x-w)] += 1
    X[min(W,x+w)] += -1
    Y[max(0,y-w)] += 1
    Y[min(H,y+w)] += -1
for i in xrange(1,W+1): X[i] += X[i-1]
for i in xrange(1,H+1): Y[i] += Y[i-1]
print "Yes" if min(X[:-1]) > 0 or min(Y[:-1]) > 0 else "No"

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

_, w, h = map(int, f.readline().split())
xyw = [list(map(int, line.split())) for line in f]

from operator import itemgetter
def check(xyw, i, size):
    xyw.sort(key=itemgetter(i))
    p = 0
    for xywi in xyw:
        if xywi[i] - xywi[2] <= p:
            p = max(p, xywi[i] + xywi[2])
    return size <= p

print('Yes' if check(xyw,0,w) or check(xyw,1,h) else 'No')

Submission status: Accepted

Solution code:
def checkable(alist,maxs):
    if alist[0][0]<=0:
        i=1
        powerleft=alist[0][1]
        loc=alist[0][0]
        next=alist[1][0]
        while(powerleft>=next-loc):
            if i<N:
                newpower=alist[i][1]
            else:
                newpower=0
            powerleft=max(powerleft-(next-loc),newpower)
            loc=next
            if i<N:
                next=alist[i+1][0]
            #print powerleft,loc,next
            i+=1
            if loc>=maxs:
                return 1
    return 0

[N,W,H]=[int(x) for x in raw_input().split()]
wlist=[[W,0]]
hlist=[[H,0]]
for i in range(N):
   [x,y,w]=[int(x) for x in raw_input().split()]
   wlist.append([x-w,2*w])
   hlist.append([y-w,2*w])
wlist.sort()
hlist.sort()
#print wlist,hlist
ans=checkable(wlist,W)|checkable(hlist,H)
if ans:
    print 'Yes'
else:
    print 'No'

Submission status: Accepted

Solution code:
N,W,H=map(int,raw_input().split())
W=W*2+1
H=H*2+1
wa=[0]*(W+1)
ha=[0]*(H+1)
for _ in xrange(N):
    x,y,w=map(int,raw_input().split())
    wa[max((x-w)*2,0)]+=1
    if (x+w+1)*2<=W: wa[(x+w+1)*2-1]-=1
    ha[max((y-w)*2,0)]+=1
    if (y+w+1)*2<=H: ha[(y+w+1)*2-1]-=1
for i in xrange(W): wa[i+1]+=wa[i]
for i in xrange(H): ha[i+1]+=ha[i]
if 0 in wa[:W] and 0 in ha[:H]:
    print "No"
else:
    print "Yes"

Submission status: Accepted

Solution code:
N, W, H = [int(x) for x in input().split()]

map_x = [0] * W
map_y = [0] * H

for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    map_x[max(0, x - w)] = max(map_x[max(0, x - w)], x + w - max(0, x - w))
    map_y[max(0, y - w)] = max(map_y[max(0, y - w)], y + w - max(0, y - w))


def check_wifi(wifi):
    m = 0
    end = len(wifi)

    for i, x in enumerate(wifi):
        if x:
            m = max(m, i + x)

        if m >= end:
            return True

        if i < m:
            continue

        return False

    return False

print('Yes' if check_wifi(map_x) or check_wifi(map_y) else 'No')

Submission status: Accepted

Solution code:
N, W, H = [int(x) for x in input().split()]

map_x = [0] * W
map_y = [0] * H

for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    map_x[max(0, x - w)] = max(map_x[max(0, x - w)], x + w - max(0, x - w))
    map_y[max(0, y - w)] = max(map_y[max(0, y - w)], y + w - max(0, y - w))


def check_wifi(wifi):
    m = 0
    end = len(wifi)

    for i, x in enumerate(wifi):
        if x and i + x > m:
            m = i + x

        if m >= end:
            return True

        if i < m:
            continue

        return False

    return False


print('Yes' if check_wifi(map_x) or check_wifi(map_y) else 'No')

Submission status: Accepted

Solution code:
N, W, H = [int(x) for x in input().split()]

map_x = [0] * W
map_y = [0] * H

for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    mx = max(0, x - w)
    map_x[mx] = max(map_x[mx], x + w - mx)
    my = max(0, y - w)
    map_y[my] = max(map_y[my], y + w - my)


def check_wifi(wifi):
    m = 0
    end = len(wifi)

    for i, x in enumerate(wifi):
        if x and i + x > m:
            m = i + x

        if m >= end:
            return True

        if i < m:
            continue

        return False

    return False


print('Yes' if check_wifi(map_x) or check_wifi(map_y) else 'No')

Submission status: Accepted

Solution code:
import sys
n,w,h = map(int,input().split())
Yoko = []
Tate = []
for i in range(n):
    x,y,r = map(int,input().split())
    Yoko.append([x - r,x + r])
    Tate.append([y - r,y + r])
Yoko = sorted(Yoko)
Tate = sorted(Tate)

if Yoko[0][0] > 0 and Tate[0][0] > 0:
    print("No")
    sys.exit()

Yoko_han = [Yoko[0][0],Yoko[0][1]]
Tate_han = [Tate[0][0],Tate[0][1]]
if Yoko[0][0] <= 0:
    if Yoko_han[1] >= w:
        print("Yes")
        sys.exit()
    else:
        for j in range(1,len(Tate)):
            if Yoko[j][0] <= Yoko_han[1] and Yoko_han[1] < Yoko[j][1]:
                Yoko_han[1] = Yoko[j][1]
                if Yoko_han[1] >= w:
                    print("Yes")
                    sys.exit()
                
            elif Yoko_han[1] < Yoko[j][0]:
                break
if Tate[0][0] > 0:
    print("No")
    sys.exit()
else:
    if Tate_han[1] >= h:
            print("Yes")
            sys.exit()
    else:
        for k in range(1,len(Yoko)):
            if Tate[k][0] <= Tate_han[1] and Tate_han[1] < Tate[k][1]:
                Tate_han[1] = Tate[k][1]
                if Tate_han[1] >= h:
                    print("Yes")
                    sys.exit()
                
            elif Yoko_han[1] < Yoko[k][0]:
                print("No")
                sys.exit()
print("No")

Submission status: Accepted

Solution code:
def f(v):
    n=0
    for i in range(len(v)-1):
        n+=v[i]
        if n<=0:return False
    return True

n,W,H=map(int,input().split())
w=[0]*(W+1)
h=[0]*(H+1)
for _ in [0]*n:
    x,y,a=map(int,input().split())
    w[max(0, x - a)]+=1
    w[min(W, x + a)]-=1
    h[max(0, y - a)]+=1
    h[min(H, y + a)]-=1
print(['No','Yes'][f(w)or f(h)])

Submission status: Accepted

Solution code:
N, W, H = map(int, input().split())
row, col = [0] * (H + 1), [0] * (W + 1)
for _ in range(N):
    x, y, w = map(int, input().split())
    row[max(0, y - w)] += 1
    row[min(H, y + w)] -= 1
    col[max(0, x - w)] += 1
    col[min(W, x + w)] -= 1
for i in range(H):
    row[i + 1] += row[i]
for i in range(W):
    col[i + 1] += col[i]
print("Yes" if all(x > 0 for x in row[:-1]) or all(x > 0 for x in col[:-1]) else "No")

Submission status: Accepted

Solution code:
N, W, H = map(int, input().split())
row, col = [0] * (H + 1), [0] * (W + 1)
for _ in range(N):
    x, y, w = map(int, input().split())
    row[max(0, y - w)] += 1
    row[min(H, y + w)] -= 1
    col[max(0, x - w)] += 1
    col[min(W, x + w)] -= 1
for i in range(H):
    row[i + 1] += row[i]
for i in range(W):
    col[i + 1] += col[i]
row.pop(), col.pop()
print("Yes" if all(x > 0 for x in row) or all(x > 0 for x in col) else "No")

Submission status: Accepted

Solution code:
N, W, H = map(int, input().split())
row, col = [0] * (H + 1), [0] * (W + 1)
for _ in range(N):
    x, y, w = map(int, input().split())
    row[max(0, y - w)] += 1
    row[min(H, y + w)] -= 1
    col[max(0, x - w)] += 1
    col[min(W, x + w)] -= 1
flag1 = flag2 = True
for i in range(H):
    row[i + 1] += row[i]
    flag1 &= row[i] > 0
if flag1:
    print("Yes")
    quit()
for i in range(W):
    col[i + 1] += col[i]
    flag2 &= col[i] > 0
if flag2:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N, W, H = map(int, input().split())
row, col = [0] * (H + 1), [0] * (W + 1)
for _ in range(N):
    x, y, w = map(int, input().split())
    row[max(0, y - w)] += 1
    row[min(H, y + w)] -= 1
    col[max(0, x - w)] += 1
    col[min(W, x + w)] -= 1
for i in range(H):
    row[i + 1] += row[i]
    if not row[i]:
        break
else:
    print("Yes")
    quit()
for i in range(W):
    col[i + 1] += col[i]
    if not col[i]:
        break
else:
    print("Yes")
    quit()
print("No")

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,w,h = LI()
        a = [LI() for _ in range(n)]
        b = []
        c = []
        for x,y,ww in a:
            b.append((x-ww,x+ww))
            c.append((y-ww,y+ww))
        b.sort()
        c.sort()
        f = False
        mi = b[0][0]
        ma = b[0][1]
        for l,r in b[1:]:
            if l > ma:
                break
            ma = max(r,ma)
        if mi <= 0 and ma >= w:
            f = True
        mi = c[0][0]
        ma = c[0][1]
        for l,r in c[1:]:
            if l > ma:
                break
            ma = max(r,ma)
        if mi <= 0 and ma >= h:
            f = True

        if f:
            rr.append('Yes')
        else:
            rr.append('No')
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
def solve():
    from itertools import accumulate
    from operator import add
    from sys import stdin
    f_i = stdin
    
    N, W, H = map(int, f_i.readline().split())
    
    X = [0] * (W + 1)
    Y = [0] * (H + 1)
    
    for i in range(N):
        x, y, w = map(int, f_i.readline().split())
        
        if x < w:
            X[0] += 1
        else:
            X[x - w] += 1
        if x + w > W:
            X[W] -= 1
        else:
            X[x + w] -= 1
        
        if y < w:
            Y[0] += 1
        else:
            Y[y - w] += 1
        if y + w > H:
            Y[H] -= 1
        else:
            Y[y + w] -= 1
    
    if 0 in accumulate(X[:-1], add) and 0 in accumulate(Y[:-1], add):
        print('No')
    else:
        print('Yes')

solve()

Submission status: Accepted

Solution code:
n,w,h=map(int,input().split())
todoku_retu=[0]*(w+1)
todoku_gyou=[0]*(h+1)
for i in range(n):
	x,y,k=map(int,input().split())
	todoku_retu[max(x-k,0)]+=1
	todoku_retu[min(x-1+k,w-1)+1]-=1
	todoku_gyou[max(y-k,0)]+=1
	todoku_gyou[min(y-1+k,h-1)+1]-=1
p=0
d=0
for i in range(len(todoku_retu)-1):
	p+=todoku_retu[i]
	if p<=0:
		d+=1
		break
p=0
for i in range(len(todoku_gyou)-1):
	p+=todoku_gyou[i]
	if p<=0:
		d+=1
		break
if d!=2:
	print("Yes")
else:
	print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())



while True:
    N,W,H = inpl()
    imosW = [0]*(W+1)
    imosH = [0]*(H+1)
    for _ in range(N):
        x,y,w = inpl()
        lx,rx = max(0,x-w),min(W-1,x+w-1)
        ly,ry = max(0,y-w),min(H-1,y+w-1)
        imosW[lx] += 1
        imosW[rx+1] -= 1
        imosH[ly] += 1
        imosH[ry+1] -= 1

    for i in range(1,W+1):
        imosW[i] += imosW[i-1]

    for i in range(1,H+1):
        imosH[i] += imosH[i-1]

    flagH = True
    flagW = True

    for i in range(W):
        if imosW[i] == 0:
            flagH = False
            break

    for i in range(H):
        if imosH[i] == 0:
            flagW = False
            break

    if flagH or flagW:
        print('Yes')
    else:
        print('No')

    #print(imosH)
    #print(imosW)
    break

Submission status: Accepted

Solution code:
N, W, H = [int(n) for n in input().split()]


xmap = [0 for _ in range(W+1)]
ymap = [0 for _ in range(H+1)]
for i in range(N):
    x, y, w = [int(n) for n in input().split()]
    l = max(x-w, 0)
    r = min(x+w, W)
    a = max(y-w, 0)
    b = min(y+w, H)
    xmap[l] += 1
    xmap[r] -= 1
    ymap[a] += 1
    ymap[b] -= 1
# print(xmap, ymap)
covered = 0
xcovered = True
for i in range(W):
    covered += xmap[i]
    if covered <= 0:
        xcovered = False
covered = 0
for i in range(H):
    covered += ymap[i]
    if covered <= 0 and not xcovered:
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
n,W,H=map(int,input().split())
tx = [0 for i in range(W)]
ty = [0 for i in range(H)]
for i in range(n):
    x,y,w=map(int,input().split())
    tx[x-(w if x-w>=0 else x)]+=1
    if x+w<W:
        tx[x+w]-=1
    ty[y-(w if y-w>=0 else y)]+=1
    if y+w<H:
        ty[y+w]-=1
tx=list(itertools.accumulate(tx))
ty=list(itertools.accumulate(ty))

f=True
for n in tx:
    if n<=0:
        f=False
if f:
    print('Yes')
    exit()
f=True
for n in ty:
    if n<=0:
        f=False
print('Yes' if f else 'No')

Submission status: Runtime Error

Solution code:
n, W, H = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(n)]

imos_h = [0] * (H + 2)
imos_w = [0] * (W + 2)

for x, y, w in X:
  imos_h[max(0, y - w)] += 1
  imos_h[min(W + 1, y + w + 1)] -= 1
  imos_w[max(0, x - w)] += 1
  imos_w[min(H + 1, x + w + 1)] -= 1
  
for h in range(H):
  imos_h[h + 1] += imos_h[h]
  
for w in range(W):
  imos_w[w + 1] += imos_w[w]

is_w = all(imos_w[w] >= 1 for w in range(W + 1))
is_h = all(imos_h[h] >= 1 for h in range(H + 1))

if is_h or is_w:
  print('Yes')
else:
  print('No')

Submission status: Runtime Error

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

wifi_list=[]
x_list = [False for i in range(w+1)]
y_list = [False for i in range(h+1)]

for i in range(n):
    input_lines = raw_input()
    xi,yi,wi = map(int, input_lines.split()))
    xs=xi-wi if xi-wi>=0 else 0
    xe=xi+wi if xi+wi<=w else w
    ys=yi-wi if yi-wi>=0 else 0
    ye=yi+wi if yi+wi<=h else h
    x_list[xs:xe+1]=True
    y_list[ys:ye+1]=True

if False in x_list or False in y_list:
    print 'No'
else:
    print 'Yes'

Submission status: Runtime Error

Solution code:
import sys

in_txt=sys.stdin.read().splitlines()

n,w,h = map(int, in_txt[0].split())

wifi_list=[]
x_list = [False for i in range(w+1)]
y_list = [False for i in range(h+1)]


for i in in_txt[1:]:
    
    xi,yi,wi = map(int, i.split())
    xs=xi-wi if xi-wi>=0 else 0
    xe=xi+wi if xi+wi<=w else w
    ys=yi-wi if yi-wi>=0 else 0
    ye=yi+wi if yi+wi<=h else h
    x_list[xs:xe+1]=True
    y_list[ys:ye+1]=True

if False in x_list or False in y_list:
    print 'No'
else:
    print 'Yes'

Submission status: Runtime Error

Solution code:
mport sys

in_txt=sys.stdin.read().splitlines()

n,w,h = map(int, in_txt[0].split())

wifi_list=[]

area = [[False for i in range(w+1)] for j in range(h+1)]

for i in in_txt[1:]:

    xi,yi,wi = map(int, i.split())
    xs=xi-wi if xi-wi>=0 else 0
    xe=xi+wi if xi+wi<=w else w
    ys=yi-wi if yi-wi>=0 else 0
    ye=yi+wi if yi+wi<=h else h

    for j in range(h+1):
        area[j][xs:xe+1]=[True]*(xe-xs+1)
    area[ys:ye+1]=[[True]*(w+1)]*(ye-ys+1)

flag=False
for i in area:
    if False in i:
        flag=True
        break

if flag:
    print 'No'
else:
    print 'Yes'

Submission status: Runtime Error

Solution code:
# your code goes here

import numpy as np

buf = raw_input()
buf = buf.split(" ")

n = int(buf[0])
w = int(buf[1])
h = int(buf[2])

array = np.zeros((h, w))

for i in xrange(n):
	buf = raw_input()
	buf = buf.split(" ")
	x = int(buf[0])
	y = int(buf[1])
	w = int(buf[2])
	array[(y-w):(y+w),:]=True
	array[:,(x-w):(x+w)]=True
	
if array.all():
	print "Yes"
else:
	print "No"

Submission status: Runtime Error

Solution code:
test_file = open('C:\\Users\\nanashi\Downloads\\2600-in21.txt')

input = lambda: test_file.readline().rstrip()


N, W, H = [int(x) for x in input().split()]

map_x = [False] * W
count_x = 0
map_y = [False] * H
count_y = 0

wifi_x = []
wifi_y = []
for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    wifi_x.append((x - w, x + w))
    wifi_y.append((y - w, y + w))
wifi_x.sort(key=lambda a: a[1], reverse=True)
wifi_y.sort(key=lambda a: a[1], reverse=True)


def check_wifi(wifi, l):
    for x1, x2 in wifi:
        if x1 <= l < x2:
            return x2
    return None


ans_x = True
b = 0
for x in range(W):
    if x < b:
        continue

    b = check_wifi(wifi_x, x)
    if not b:
        ans_x = False
        break

if not ans_x:
    b = 0
    for y in range(H):
        if y < b:
            continue

        b = check_wifi(wifi_y, y)
        if not b:
            print('No')
            exit()

print('Yes')