結果

問題 No.2338 Range AtCoder Query
ユーザー とりゐ
提出日時 2023-06-02 23:33:58
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,841 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 648,180 KB
最終ジャッジ日時 2024-12-28 23:26:35
合計ジャッジ時間 81,957 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 RE * 12 TLE * 14 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

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(0)
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]+=1
  if Si=='AC':
    cnt[Pi]+=1
    if cnt[Pi]==1:
      cnt_ac+=1
      cnt_wa+=memo[Pi][-1]-1
    memo[Pi].append(0)

def AddL(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  if Si=='AC':
    memo[Pi].appendleft(0)
  memo[Pi][0]+=1
  if Si=='AC':
    cnt[Pi]+=1
    if cnt[Pi]==1:
      cnt_ac+=1
    else:
      cnt_wa-=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]-=1
  if Si=='AC':
    memo[Pi].pop()
    memo[Pi][-1]-=1
    cnt[Pi]-=1
    if cnt[Pi]==0:
      cnt_ac-=1
      cnt_wa-=memo[Pi][-1]

def DelL(idx):
  global cnt_ac
  global cnt_wa
  Pi=P[idx]
  Si=S[idx]
  memo[Pi][0]-=1
  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+=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