結果

問題 No.2421 entersys?
ユーザー ntuda
提出日時 2023-08-13 23:23:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,459 ms / 3,000 ms
コード長 1,929 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 295,300 KB
最終ジャッジ日時 2024-11-21 17:29:40
合計ジャッジ時間 23,287 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import *


def update(k, x):
    k += N0 - 1
    data[k] += x  # 加算にするなら+=に
    while k >= 0:
        k = (k - 1) // 2
        data[k] = data[2 * k + 1] + data[2 * k + 2]


def query(l, r):
    s = 0
    L = l + N0;
    R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R - 1]
        if L & 1:
            s += data[L - 1]
            L += 1
        L >>= 1;
        R >>= 1
    return s


from collections import defaultdict

dic = defaultdict(list)
dic2 = defaultdict(list)

N = int(input())
A = set()
LR = []
for i in range(N):
    x, l, r = input().split()
    l = int(l)
    r = int(r) + 1
    LR.append((l, r))
    A.add(l)
    A.add(r)
    dic[x].append(l)
    dic[x].append(r)
    dic2[x].append((0, l))
Q = int(input())
QUE = []
for i in range(Q):
    que = input().split()
    QUE.append((*que, i + 1))
    if que[0] == "3":
        x, l, r = que[1:]
        l = int(l)
        r = int(r) + 1
        A.add(l)
        A.add(r)
        dic[x].append(l)
        dic[x].append(r)
        dic2[x].append((i + 1, l))
    if que[0] == "2":
        t = int(que[1])
        A.add(t)
for k in dic.keys():
    dic[k].sort()
    dic2[k].sort(key=lambda x: x[1])

A = sorted(list(A))
NA = len(A)
D = dict(zip(A, range(NA)))
# N: 処理する区間の長さ
N0 = 2 ** (NA + 1).bit_length()
data = [0] * (2 * N0)

for l, r in LR:
    update(D[l], 1)
    update(D[r], -1)
for i in range(Q):
    if QUE[i][0] == "1":
        x = QUE[i][1]
        t = int(QUE[i][2])
        a = bisect_right(dic[x], t)
        if a % 2 == 0:
            print("No")
        elif dic2[x][a // 2][0] < i + 1:
            print("Yes")
        else:
            print("No")
    elif QUE[i][0] == "2":
        t = int(QUE[i][1])
        print(query(0, D[t] + 1))
    else:
        l, r = QUE[i][2:4]
        l = int(l)
        r = int(r) + 1
        update(D[l], 1)
        update(D[r], -1)
0