結果

問題 No.2421 entersys?
ユーザー ntudantuda
提出日時 2023-08-13 23:23:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,269 ms / 3,000 ms
コード長 1,929 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 295,480 KB
最終ジャッジ日時 2024-05-01 13:00:07
合計ジャッジ時間 21,963 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
55,644 KB
testcase_01 AC 57 ms
65,788 KB
testcase_02 AC 80 ms
76,756 KB
testcase_03 AC 46 ms
62,620 KB
testcase_04 AC 52 ms
66,168 KB
testcase_05 AC 70 ms
73,640 KB
testcase_06 AC 70 ms
73,904 KB
testcase_07 AC 70 ms
73,996 KB
testcase_08 AC 77 ms
77,020 KB
testcase_09 AC 93 ms
77,856 KB
testcase_10 AC 69 ms
72,348 KB
testcase_11 AC 1,016 ms
233,988 KB
testcase_12 AC 989 ms
234,140 KB
testcase_13 AC 995 ms
234,888 KB
testcase_14 AC 1,048 ms
234,416 KB
testcase_15 AC 1,050 ms
235,000 KB
testcase_16 AC 1,063 ms
244,428 KB
testcase_17 AC 1,025 ms
244,564 KB
testcase_18 AC 996 ms
245,332 KB
testcase_19 AC 992 ms
244,836 KB
testcase_20 AC 1,006 ms
244,440 KB
testcase_21 AC 734 ms
211,072 KB
testcase_22 AC 784 ms
231,676 KB
testcase_23 AC 1,248 ms
284,028 KB
testcase_24 AC 1,269 ms
295,480 KB
testcase_25 AC 1,251 ms
282,772 KB
testcase_26 AC 649 ms
191,852 KB
testcase_27 AC 666 ms
191,656 KB
testcase_28 AC 664 ms
193,644 KB
権限があれば一括ダウンロードができます

ソースコード

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