結果

問題 No.2338 Range AtCoder Query
ユーザー とりゐとりゐ
提出日時 2023-06-02 23:31:00
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,912 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 87,204 KB
実行使用メモリ 503,704 KB
最終ジャッジ日時 2023-08-28 06:09:42
合計ジャッジ時間 9,975 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
72,028 KB
testcase_01 AC 90 ms
72,080 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 90 ms
71,972 KB
testcase_05 RE -
testcase_06 AC 173 ms
80,560 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます

ソースコード

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