結果

問題 No.1557 Binary Variable
ユーザー raven7959raven7959
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 383 ms
170,380 KB
testcase_01 AC 402 ms
135,296 KB
testcase_02 AC 39 ms
52,096 KB
testcase_03 AC 39 ms
52,480 KB
testcase_04 AC 480 ms
100,680 KB
testcase_05 AC 486 ms
100,788 KB
testcase_06 AC 445 ms
100,480 KB
testcase_07 AC 475 ms
100,652 KB
testcase_08 AC 551 ms
100,696 KB
testcase_09 AC 567 ms
100,740 KB
testcase_10 AC 656 ms
110,592 KB
testcase_11 AC 689 ms
111,744 KB
testcase_12 AC 536 ms
100,736 KB
testcase_13 AC 659 ms
113,664 KB
testcase_14 AC 908 ms
167,684 KB
testcase_15 AC 662 ms
117,376 KB
testcase_16 AC 908 ms
167,168 KB
testcase_17 AC 827 ms
158,464 KB
testcase_18 AC 792 ms
152,448 KB
testcase_19 AC 1,001 ms
196,284 KB
testcase_20 AC 984 ms
195,460 KB
testcase_21 AC 971 ms
195,440 KB
testcase_22 AC 1,002 ms
196,172 KB
testcase_23 AC 998 ms
195,340 KB
testcase_24 AC 1,015 ms
258,356 KB
testcase_25 AC 1,020 ms
258,120 KB
testcase_26 AC 1,055 ms
259,584 KB
testcase_27 AC 1,039 ms
258,560 KB
testcase_28 AC 1,028 ms
265,728 KB
testcase_29 AC 1,029 ms
264,576 KB
testcase_30 AC 1,049 ms
264,960 KB
testcase_31 AC 1,051 ms
264,320 KB
testcase_32 AC 1,077 ms
265,216 KB
testcase_33 AC 958 ms
188,776 KB
testcase_34 AC 39 ms
52,096 KB
testcase_35 AC 37 ms
52,480 KB
testcase_36 AC 36 ms
52,480 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