結果

問題 No.2421 entersys?
ユーザー ntudantuda
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,692 KB
testcase_01 AC 53 ms
65,584 KB
testcase_02 AC 81 ms
76,928 KB
testcase_03 AC 50 ms
62,728 KB
testcase_04 AC 56 ms
66,324 KB
testcase_05 AC 72 ms
73,864 KB
testcase_06 AC 74 ms
74,144 KB
testcase_07 AC 77 ms
74,132 KB
testcase_08 AC 80 ms
76,508 KB
testcase_09 AC 101 ms
77,616 KB
testcase_10 AC 68 ms
73,488 KB
testcase_11 AC 1,047 ms
234,100 KB
testcase_12 AC 1,036 ms
233,828 KB
testcase_13 AC 1,043 ms
234,856 KB
testcase_14 AC 1,058 ms
234,372 KB
testcase_15 AC 1,079 ms
234,776 KB
testcase_16 AC 1,061 ms
244,536 KB
testcase_17 AC 1,089 ms
244,540 KB
testcase_18 AC 1,049 ms
244,964 KB
testcase_19 AC 1,049 ms
244,308 KB
testcase_20 AC 1,064 ms
244,148 KB
testcase_21 AC 779 ms
210,972 KB
testcase_22 AC 855 ms
231,828 KB
testcase_23 AC 1,357 ms
283,792 KB
testcase_24 AC 1,459 ms
295,300 KB
testcase_25 AC 1,396 ms
282,948 KB
testcase_26 AC 769 ms
191,836 KB
testcase_27 AC 707 ms
193,684 KB
testcase_28 AC 716 ms
193,248 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