結果

問題 No.2974 関数の芽
ユーザー ねしんねしん
提出日時 2024-11-29 23:48:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,464 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 164,964 KB
最終ジャッジ日時 2024-11-29 23:48:50
合計ジャッジ時間 22,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
55,552 KB
testcase_01 AC 52 ms
55,936 KB
testcase_02 AC 49 ms
55,936 KB
testcase_03 AC 48 ms
56,192 KB
testcase_04 AC 48 ms
55,936 KB
testcase_05 AC 47 ms
56,064 KB
testcase_06 AC 48 ms
55,936 KB
testcase_07 AC 48 ms
57,088 KB
testcase_08 AC 52 ms
56,832 KB
testcase_09 WA -
testcase_10 AC 49 ms
55,936 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 839 ms
151,736 KB
testcase_15 AC 850 ms
155,676 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
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+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)),GMST2.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")
0