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((K,-L,i)) elif K<0: FM.append((K,-L,i)) if M>0: GP.append((M,-N,i)) elif M<0: GM.append((M,-N,i)) query.append((K,L,M,N,X)) FP.sort(key=cmp_to_key(cmp)) FM.sort(key=cmp_to_key(cmp)) GP.sort(key=cmp_to_key(cmp)) GM.sort(key=cmp_to_key(cmp)) Find=[-1]*Q Gind=[-1]*Q FPS=[] FMS=[] GPS=[] GMS=[] for i in range(len(FP)): Find[FP[i][2]]=i FPS.append((FP[i][1]/FP[i][0])) for i in range(len(FM)): Find[FM[i][2]]=i FMS.append((FM[i][1]/FM[i][0])) for i in range(len(GP)): Gind[GP[i][2]]=i GPS.append((GP[i][1]/GP[i][0])) for i in range(len(GM)): Gind[GM[i][2]]=i GMS.append((GM[i][1]/GM[i][0])) def PLUS(a,b): return a+b FPST=SegTree(PLUS,0,len(FP)) FMST=SegTree(PLUS,0,len(FM)) GPST=SegTree(PLUS,0,len(GP)) GMST=SegTree(PLUS,0,len(GM)) FPST2=SegTree(PLUS,0,len(FP)) FMST2=SegTree(PLUS,0,len(FM)) GPST2=SegTree(PLUS,0,len(GP)) GMST2=SegTree(PLUS,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),FPST2.prod(0,c)] c=bisect.bisect_right(FMS,z) T=[FMST.prod(c,len(FM)),FMST2.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),GPST2.prod(0,c)] c=bisect.bisect_right(GMS,z) A=[GMST.prod(c,len(GM)),GPST2.prod(0,c)] 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) FPST2.set(Find[i],l) elif k==0: ft+=max(0,l) else: FMST.set(Find[i],k) FMST2.set(Find[i],l) if m>0: GPST.set(Gind[i],m) GPST2.set(Gind[i],n) elif m==0: gt+=max(0,n) else: GMST.set(Gind[i],m) GMST2.set(Gind[i],n) if check((x*Z-1),Z) and check(x*Z+1,Z): print("Yes") else: print("No")