結果

問題 No.2338 Range AtCoder Query
ユーザー とりゐとりゐ
提出日時 2023-06-02 23:40:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,171 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 673,480 KB
最終ジャッジ日時 2024-12-28 23:54:20
合計ジャッジ時間 103,330 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
59,648 KB
testcase_01 AC 41 ms
62,664 KB
testcase_02 AC 41 ms
60,160 KB
testcase_03 AC 42 ms
62,072 KB
testcase_04 AC 42 ms
283,328 KB
testcase_05 AC 40 ms
59,648 KB
testcase_06 AC 123 ms
85,488 KB
testcase_07 AC 119 ms
83,416 KB
testcase_08 AC 120 ms
84,804 KB
testcase_09 AC 121 ms
83,200 KB
testcase_10 AC 119 ms
365,084 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 MLE -
testcase_27 MLE -
testcase_28 MLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 AC 1,451 ms
268,444 KB
testcase_34 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

debug=0
if debug:
  import random
from collections import deque

if debug:
  N,M,Q=10,10,10
else:
  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):
  if debug:
    P[i]=random.randint(1,M)
    if random.randint(1,2)==1:
      S[i]='AC'
    else:
      S[i]='WA'
  else:
    P[i],S[i]=input().split()
    P[i]=int(P[i])
m=int(Q**0.5)+1
bucket=[[] for i in range(m)]
if debug:
  print(P)
  print(S)
for i in range(Q):
  if debug:
    l=random.randint(0,N-1)
    r=random.randint(0,N-1)
    print(l,r)
    if r<l:
      l,r=r,l
  else:
    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
  
 
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