結果

問題 No.2974 関数の芽
ユーザー ねしんねしん
提出日時 2024-11-29 23:52:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,210 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 188,316 KB
最終ジャッジ日時 2024-11-29 23:52:59
合計ジャッジ時間 20,308 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
55,552 KB
testcase_01 AC 55 ms
55,808 KB
testcase_02 AC 56 ms
55,552 KB
testcase_03 AC 49 ms
55,936 KB
testcase_04 AC 49 ms
55,936 KB
testcase_05 AC 47 ms
55,424 KB
testcase_06 AC 48 ms
56,064 KB
testcase_07 AC 50 ms
56,064 KB
testcase_08 AC 62 ms
56,320 KB
testcase_09 AC 52 ms
56,704 KB
testcase_10 AC 48 ms
55,936 KB
testcase_11 AC 66 ms
66,176 KB
testcase_12 AC 142 ms
77,440 KB
testcase_13 AC 459 ms
91,288 KB
testcase_14 AC 716 ms
149,032 KB
testcase_15 AC 726 ms
152,552 KB
testcase_16 AC 1,946 ms
184,464 KB
testcase_17 AC 1,957 ms
184,484 KB
testcase_18 AC 1,961 ms
184,576 KB
testcase_19 AC 1,929 ms
184,804 KB
testcase_20 AC 1,936 ms
185,112 KB
testcase_21 AC 1,943 ms
184,652 KB
testcase_22 TLE -
testcase_23 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 i<ii:
    return 1
  else:
    return -1
    
Q=int(input())
query=[]
FP=[]
FM=[]
GP=[]
GM=[]
for i in range(Q):
  K,L,M,N,X=list(map(int,input().split()))
  if K>0:
    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[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**9
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")
0