結果

問題 No.1557 Binary Variable
ユーザー raven7959
提出日時 2021-08-20 16:17:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,077 ms / 2,000 ms
コード長 1,561 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 265,728 KB
最終ジャッジ日時 2024-10-13 19:27:35
合計ジャッジ時間 31,003 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M=map(int,input().split())
L=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
L=sorted(L,key=lambda x:x[1])
LS=set()
for l,r in L:
  LS.add(l)
  LS.add(r)
LS=sorted(list(LS))
D={LS[i]:i for i in range(len(LS))}
n=len(LS)
class segtree():
  n=1
  size=1
  log=2
  d=[0]
  op=None
  e=10**15
  def update(self,k):
    self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
  def __init__(self,V,OP,E): #初期値(配列),演算,単位元で初期化
    self.n=len(V)
    self.op=OP
    self.e=E
    self.log=(self.n-1).bit_length()
    self.size=1<<self.log
    self.d=[E for i in range(2*self.size)]
    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): #1点更新
    assert 0<=p and 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): #1点取得
    assert 0<=p and p<self.n
    return self.d[p+self.size]
  def prod(self,l,r): #区間取得
    assert 0<=l and l<=r and r<=self.n
    sml=self.e
    smr=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):
        smr=self.op(self.d[r-1],smr)
        r-=1
      l>>=1
      r>>=1
    return self.op(sml,smr)
  def all_prod(self): #全区間取得
    return self.d[1]
V=[1]*n
def OP(x,y):
  return min(x,y)
seg=segtree(V,OP,2)
cnt=0
for i in range(M):
  l,r=D[L[i][0]],D[L[i][1]]
  if seg.prod(l,r+1)==0:
    pass
  else:
    seg.set(r,0)
    cnt+=1
print(N-cnt)
0