結果

問題 No.2974 関数の芽
ユーザー ねしんねしん
提出日時 2024-11-30 00:04:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,705 ms / 2,000 ms
コード長 3,133 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 166,732 KB
最終ジャッジ日時 2024-11-30 00:04:54
合計ジャッジ時間 17,227 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
57,132 KB
testcase_01 AC 46 ms
57,332 KB
testcase_02 AC 48 ms
56,188 KB
testcase_03 AC 47 ms
57,200 KB
testcase_04 AC 47 ms
57,660 KB
testcase_05 AC 47 ms
56,812 KB
testcase_06 AC 49 ms
57,028 KB
testcase_07 AC 49 ms
57,768 KB
testcase_08 AC 49 ms
56,804 KB
testcase_09 AC 49 ms
57,264 KB
testcase_10 AC 50 ms
56,480 KB
testcase_11 AC 64 ms
67,192 KB
testcase_12 AC 130 ms
77,164 KB
testcase_13 AC 441 ms
88,096 KB
testcase_14 AC 713 ms
126,936 KB
testcase_15 AC 706 ms
129,268 KB
testcase_16 AC 1,465 ms
162,576 KB
testcase_17 AC 1,524 ms
164,096 KB
testcase_18 AC 1,504 ms
164,544 KB
testcase_19 AC 1,542 ms
164,196 KB
testcase_20 AC 1,565 ms
163,864 KB
testcase_21 AC 1,550 ms
163,820 KB
testcase_22 AC 1,614 ms
165,344 KB
testcase_23 AC 1,705 ms
166,732 KB
権限があれば一括ダウンロードができます

ソースコード

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=[]
H=10**30
for i in range(Q):
  K,L,M,N,X=list(map(int,input().split()))
  if K>0:
    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")
0