結果

問題 No.2338 Range AtCoder Query
ユーザー とりゐとりゐ
提出日時 2023-06-02 23:42:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,208 bytes
コンパイル時間 1,064 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 214,324 KB
最終ジャッジ日時 2024-06-09 02:11:08
合計ジャッジ時間 9,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
59,776 KB
testcase_01 AC 43 ms
54,656 KB
testcase_02 AC 44 ms
54,528 KB
testcase_03 AC 42 ms
54,400 KB
testcase_04 AC 42 ms
54,400 KB
testcase_05 AC 41 ms
54,400 KB
testcase_06 AC 122 ms
78,464 KB
testcase_07 AC 117 ms
77,664 KB
testcase_08 AC 117 ms
77,440 KB
testcase_09 AC 122 ms
78,208 KB
testcase_10 AC 119 ms
77,900 KB
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]

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])
    if S[i]=='WA':
      S[i]=0
    else:
      S[i]=1
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==1:
    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==1:
    memo[Pi].appendleft(0)
  memo[Pi][0]+=1
  if Si==1:
    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==0:
    memo[Pi][-1]-=1
  if Si==1:
    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==0:
    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