結果

問題 No.1439 Let's Compare!!!!
コンテスト
ユーザー persimmon-persimmon
提出日時 2021-06-10 09:53:22
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,997 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 94,700 KB
最終ジャッジ日時 2024-11-29 15:27:53
合計ジャッジ時間 2,790 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 0-indexed binary indexed tree
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  # sum of [0,i) sum(a[:i])
  def sum(self, i):
    if i==0:return 0
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    i+=1
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  # sum of [l,r)   sum(a[l:r])
  def sumlr(self, i, j):
    return self.sum(j) - self.sum(i)
  # a[i]
  def get(self,i):
    i+=1
    return self.el[i]
def main0(n,s,t,sary,tary,query):
  ret=[]
  for tmp in query:
    c,x,y=tmp.split()
    x=int(x)
    y=int(y)
    if c=="S":
      s-=pow(10,n-x)*sary[x-1]
      s+=pow(10,n-x)*y
      sary[x-1]=y
    else:
      t-=pow(10,n-x)*tary[x-1]
      t+=pow(10,n-x)*y
      tary[x-1]=y
    #print(s,t)
    if s>t:
      ret.append(">")
    elif s==t:
      ret.append("=")
    else:
      ret.append("<")
  return ret

def main1(n,s,t,sary,tary,query):
  dary=[abs(x-y) for x,y in zip(sary,tary)]
  bit=BIT(n)
  for i,x in enumerate(dary):
    bit.add(i,x)
  ret=[]
  for tmp in query:
    c,x,y=tmp.split()
    x=int(x)
    y=int(y)
    pre=dary[x-1]
    if c=="S":
      sary[x-1]=y
    else:
      tary[x-1]=y
    dary[x-1]=abs(sary[x-1]-tary[x-1])
    bit.add(x-1,-pre+dary[x-1])
    l,r=0,n+1
    while r-l>1:
      x=(r+l)//2
      if bit.sum(x)!=0:
        l,r=l,x
      else:
        l,r=x,r
    #print(*sary,sep="")
    #print(*tary,sep="")
    #print(*dary,sep="")
    #print(l)
    ans="="
    for j in range(l-2,l+2):
      if j<1:continue
      if n<j:break
      tmp=bit.sum(j)
      if tmp==0:continue
      if sary[j-1]<tary[j-1]:
        ans="<"
      else:
        ans=">"
      break
    ret.append(ans)
  return ret
"""
9
539528971
622993619
4
T 6 9
S 5 6
T 8 1
S 9 5
"""
if __name__=='__main__':
  n=int(input())
  s=input()
  sary=list(map(int,list(s)))
  s=int(s)
  t=input()
  tary=list(map(int,list(t)))
  t=int(t)
  q=int(input())
  query=[input() for _ in range(q)]
  #ret0=main0(n,s,t,sary[:],tary[:],query[:])
  ret1=main1(n,s,t,sary[:],tary[:],query[:])
  #print(ret0)
  print(*ret1,sep="\n")

from random import randint
if __name__=='__main__1':
  for _ in range(100):
    n=randint(2,4)
    s=randint(10**(n-1),10**n-1)
    t=randint(10**(n-1),10**n-1)
    sary=list(map(int,list(str(s))))
    tary=list(map(int,list(str(t))))
    q=4
    query=[]
    for _ in range(q):
      c=["S","T"][randint(0,1)]
      x=str(randint(1,n))
      y=str(randint(1,9))
      query.append(" ".join([c,x,y]))
    try:
      ret1=main1(n,s,t,sary[:],tary[:],query[:])
      ret0=main0(n,s,t,sary[:],tary[:],query[:])
      if ret0!=ret1:
        print(n)
        print(s)
        print(t)
        print(q)
        print(*query,sep="\n")
        print(ret0)
        print(ret1)
        break
    except Exception as e:
      print(e)
      print(n)
      print(s)
      print(t)
      print(q)
      print(*query,sep="\n")
      exit()
0