from functools import cmp_to_key class SegTree: def __init__(self, op, e, n, v=None): self._n = n self._op = op self._e = e self._log = (n - 1).bit_length() self._size = 1 << self._log self._d = [self._e] * (2 * self._size) if v is not None: for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._update(i) def set(self, p, x): assert 0 <= p < self._n p += self._size self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p): assert 0 <= p < self._n return self._d[p + self._size] def prod(self, l, r): assert 0 <= l <= r <= self._n sml, smr = self._e, self._e l += self._size r += self._size while l < r: if l & 1: sml = self._op(sml, self._d[l]) l += 1 if r & 1: r -= 1 smr = self._op(self._d[r], smr) l >>= 1 r >>= 1 return self._op(sml, smr) def all_prod(self): return self._d[1] def _update(self, k): self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) #https://qiita.com/AkariLuminous/items/32cbf5bc3ffb2f84a898 def cmp(a,b): k,l,i=a kk,ll,ii=b if l*kk>k*ll: return 1 elif l*kk==k*ll and i0: FP.append(((-L*H)//K,i)) elif K<0: FM.append(((-L*H)/K,i)) if M>0: GP.append(((-N*H)/M,i)) elif M<0: GM.append(((-N*H)/M,i)) query.append((K,L,M,N,X)) FP.sort() FM.sort() GP.sort() GM.sort() Find=[-1]*Q Gind=[-1]*Q FPS=[] FMS=[] GPS=[] GMS=[] for i in range(len(FP)): Find[FP[i][1]]=i FPS.append((FP[i][0]/H)) for i in range(len(FM)): Find[FM[i][1]]=i FMS.append((FM[i][0]/H)) for i in range(len(GP)): Gind[GP[i][1]]=i GPS.append((GP[i][0]/H)) for i in range(len(GM)): Gind[GM[i][1]]=i GMS.append((GM[i][0]/H)) def PLUS(a,b): return (a[0]+b[0],a[1]+b[1]) FPST=SegTree(PLUS,(0,0),len(FP)) FMST=SegTree(PLUS,(0,0),len(FM)) GPST=SegTree(PLUS,(0,0),len(GP)) GMST=SegTree(PLUS,(0,0),len(GM)) import bisect ft=0 gt=0 Z=10**10 def check(x,y): z=x/y c=bisect.bisect_left(FPS,z) U=FPST.prod(0,c) c=bisect.bisect_right(FMS,z) T=FMST.prod(c,len(FM)) Z=[U[0]+T[0],U[1]+T[1]+ft] c=bisect.bisect_left(GPS,z) B=GPST.prod(0,c) c=bisect.bisect_right(GMS,z) A=GMST.prod(c,len(GM)) R=[A[0]+B[0],A[1]+B[1]+gt] #print(Z,R) if Z[0]==R[0] and Z[1]==R[1]: return 1 else: return 0 for i in range(Q): k,l,m,n,x=query[i] if k>0: FPST.set(Find[i],(k,l)) elif k==0: ft+=max(0,l) else: FMST.set(Find[i],(k,l)) if m>0: GPST.set(Gind[i],(m,n)) elif m==0: gt+=max(0,n) else: GMST.set(Gind[i],(m,n)) if check((x*Z-1),Z) and check(x*Z+1,Z): print("Yes") else: print("No")