結果

問題 No.2338 Range AtCoder Query
ユーザー とりゐ
提出日時 2023-06-02 23:31:00
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,912 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 995,456 KB
最終ジャッジ日時 2024-12-28 23:14:59
合計ジャッジ時間 84,975 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 RE * 7 TLE * 10 MLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
input=lambda :stdin.readline()[:-1]

from collections import deque
N,M,Q=map(int,input().split())
memo=[deque() for i in range(M+1)]
for i in range(M+1):
  memo[i].append(deque())
P,S=[0]*N,[0]*N
for i in range(N):
  P[i],S[i]=input().split()
  P[i]=int(P[i])
m=int(Q**0.5)+1
bucket=[[] for i in range(m)]

for i in range(Q):
  l,r=map(lambda x:int(x)-1,input().split())
  bucket[l*m//N].append((l,r,i))
 
for i in range(m):
  if i&1:
    bucket[i].sort(key=lambda x:-x[1])
  else:
    bucket[i].sort(key=lambda x:x[1])

cnt=[0]*(M+1)
cnt_ac=0
cnt_wa=0

def AddR(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  memo[Pi][-1].append(Si)
  if Si=='AC':
    cnt[Pi]+=1
    if cnt[Pi]==1:
      cnt_ac+=1
      cnt_wa+=len(memo[Pi][-1])-1
    memo[Pi].append(deque())

def AddL(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  if Si=='AC':
    memo[Pi].appendleft(deque())
  memo[Pi][0].appendleft(Si)
  if Si=='AC':
    cnt[Pi]+=1
    if cnt[Pi]==1:
      cnt_ac+=1
    else:
      cnt_wa-=len(memo[Pi][1])-1
  elif cnt[Pi]!=0:
    cnt_wa+=1

def DelR(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  if Si=='WA':
    memo[Pi][-1].pop()
  if Si=='AC':
    memo[Pi].pop()
    memo[Pi][-1].pop()
    cnt[Pi]-=1
    if cnt[Pi]==0:
      cnt_ac-=1
      cnt_wa-=len(memo[Pi][-1])

def DelL(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  memo[Pi][0].popleft()
  if Si=='WA':
    if cnt[Pi]:
      cnt_wa-=1
  else:
    memo[Pi].popleft()
    cnt[Pi]-=1
    if cnt[Pi]==0:
      cnt_ac-=1
    else:
      cnt_wa+=len(memo[Pi][0])-1
  
cnt=[0]*N
res=0
 
ans=[0]*Q
L,R=0,0
AddR(0)


 
for b in bucket:
  for l,r,id in b:
    while R<r:
      R+=1
      AddR(R)
    while L>l:
      L-=1
      AddL(L)
    while R>r:
      DelR(R)
      R-=1
    while L<l:
      DelL(L)
      L+=1
    ans[id]=(cnt_ac,cnt_wa)
    
for i in ans:
  print(*i)
0