結果

問題 No.1557 Binary Variable
ユーザー raven7959raven7959
提出日時 2021-08-20 16:17:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,220 ms / 2,000 ms
コード長 1,561 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 266,112 KB
最終ジャッジ日時 2024-04-21 21:05:26
合計ジャッジ時間 33,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 440 ms
170,624 KB
testcase_01 AC 467 ms
135,168 KB
testcase_02 AC 37 ms
52,736 KB
testcase_03 AC 37 ms
52,864 KB
testcase_04 AC 557 ms
100,676 KB
testcase_05 AC 571 ms
100,784 KB
testcase_06 AC 524 ms
100,280 KB
testcase_07 AC 557 ms
100,908 KB
testcase_08 AC 639 ms
100,820 KB
testcase_09 AC 668 ms
100,864 KB
testcase_10 AC 782 ms
111,232 KB
testcase_11 AC 758 ms
112,256 KB
testcase_12 AC 625 ms
100,528 KB
testcase_13 AC 788 ms
113,792 KB
testcase_14 AC 1,055 ms
167,580 KB
testcase_15 AC 789 ms
117,848 KB
testcase_16 AC 1,051 ms
166,556 KB
testcase_17 AC 965 ms
158,720 KB
testcase_18 AC 945 ms
152,572 KB
testcase_19 AC 1,154 ms
196,208 KB
testcase_20 AC 1,109 ms
195,844 KB
testcase_21 AC 1,100 ms
195,736 KB
testcase_22 AC 1,109 ms
196,240 KB
testcase_23 AC 1,133 ms
195,736 KB
testcase_24 AC 1,136 ms
258,436 KB
testcase_25 AC 1,142 ms
258,436 KB
testcase_26 AC 1,180 ms
259,456 KB
testcase_27 AC 1,165 ms
258,924 KB
testcase_28 AC 1,195 ms
266,112 KB
testcase_29 AC 1,190 ms
264,620 KB
testcase_30 AC 1,184 ms
265,216 KB
testcase_31 AC 1,187 ms
264,320 KB
testcase_32 AC 1,220 ms
264,988 KB
testcase_33 AC 1,120 ms
188,776 KB
testcase_34 AC 39 ms
52,864 KB
testcase_35 AC 38 ms
52,480 KB
testcase_36 AC 38 ms
52,864 KB
権限があれば一括ダウンロードができます

ソースコード

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