結果

問題 No.2338 Range AtCoder Query
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-24 01:45:07
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,449 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 598 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 237,272 KB
最終ジャッジ日時 2026-07-24 01:45:15
合計ジャッジ時間 8,398 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2338

import math
from collections import deque

def main():
    N, M, Q = map(int, input().split())
    ps = []
    for _ in range(N):
        p, s = input().split()
        s_ = (1 if s == "AC" else 0)
        ps.append((int(p) - 1, s_))
    lr = []
    for _ in range(Q):
        l, r = map(int, input().split())
        lr.append((l - 1, r - 1))
    
    # Mo's Algorithm
    sqrt_n = int(math.sqrt(N))
    lr2 = []
    for i in range(Q):
        l, r = lr[i]
        l0 = l // sqrt_n
        lr2.append((l0, i, l, r))
    lr2.sort(key=lambda x: x[0] * (2 * N) - r)

    deques = [deque([0]) for _ in range(M)]
    wa_count = 0
    ac_count = 0
    for i in range(N):
        p, s = ps[i]
        if s == 0:
            deques[p][-1] += 1
        else:
            deques[p].append(0)
    for i in range(M):
        if len(deques[i]) >= 2:
            ac_count += 1
            wa_count += deques[i][0]

    class Interval:

        def __init__(self, ac_count , wa_count, deques, ps):
            self.ac_count = ac_count
            self.wa_count = wa_count
            self.deques = deques
            self.ps = ps

        def delete_from_left(self, index):
            p, s = self.ps[index]
            deq = self.deques[p]
            if s == 0:
                deq[0] -= 1
                if len(deq) > 1:
                    self.wa_count -= 1
            else:
                deq.popleft()
                self.ac_count -= 1
                if len(deq) > 1:
                    self.ac_count += 1
                    self.wa_count += deq[0]

        def add_from_left(self, index):
            p, s = self.ps[index]
            deq = self.deques[p]
            if s == 0:
                deq[0] += 1
                if len(deq) > 1:
                    self.wa_count += 1
            else:
                if len(deq) > 1:
                    w = deq[0]
                    self.wa_count -= w
                    self.ac_count -= 1
                deq.appendleft(0)
                self.ac_count += 1

        def delete_from_right(self, index):
            p, s = self.ps[index]
            deq = self.deques[p]
            if s == 0:
                deq[-1] -= 1
            else:
                deq.pop()
                if len(deq) == 1:
                    self.wa_count -= deq[0]
                    self.ac_count -= 1

        def add_from_right(self, index):
            p, s = self.ps[index]
            deq = self.deques[p]
            if s == 0:
                deq[-1] += 1
            else:
                if len(deq) == 1:
                    self.wa_count += deq[0]
                    self.ac_count += 1
                deq.append(0)

    interval = Interval(ac_count, wa_count, deques, ps)
    answers = [[0, 0] for _ in range(Q)]
    left = 0
    right = N - 1
    for _, q_index, l0, r0 in lr2:

        while l0 < left:
            left -= 1
            interval.add_from_left(left)
        while right < r0:
            right += 1
            interval.add_from_right(right)

        while left < l0:
            interval.delete_from_left(left)
            left += 1
        while r0 < right:
            interval.delete_from_right(right)
            right -= 1

        answers[q_index][0] = interval.ac_count
        answers[q_index][1] = interval.wa_count

    for i in range(Q):
        a, w = answers[i]
        print(a, w)
    






if __name__ == "__main__":
    main()
0