結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-07-20 11:56:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,063 ms / 3,000 ms |
コード長 | 2,514 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 281,004 KB |
最終ジャッジ日時 | 2024-09-20 11:15:23 |
合計ジャッジ時間 | 33,843 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
class segt:def __init__(self, n, ele, calc):self.num = 2 ** (n - 1).bit_length()self.el = eleself.data = [ele] * (2 * self.num)self.calc = calcdef update(self, idx, x):idx += self.num - 1self.data[idx] = xwhile idx > 0:idx = (idx - 1) // 2self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])def renew(self, idx, x):self.update(idx, self.calc(self.get(idx), x))def prod(self, left, right):l = left + self.numr = right + self.numres = self.elwhile l < r:if l % 2:res = self.calc(res, self.data[l-1])l += 1if r % 2:r -= 1res = self.calc(res, self.data[r-1])l //= 2r //= 2return resdef get(self, idx):return self.data[idx+self.num-1]def add(x, y):return x + ydef cc(a):b = sorted(a)d = dict()cnt = 0for v in b:if v not in d:d[v] = cntcnt += 1res = [d[v] for v in a]return dn = int(input())tm = []ls = [list(map(str, input().split())) for _ in range(n)]d = dict()for i in range(n):s, l, r = ls[i]l, r = int(l), int(r)ls[i][1:] = [l, r]tm.append(l)tm.append(r)if s not in d:d[s] = []d[s].append(l)d[s].append(r)q = int(input())qr = [list(map(str, input().split())) for _ in range(q)]for i in range(q):qr[i][0] = int(qr[i][0])if qr[i][0] == 1:qr[i][2] = int(qr[i][2])tm.append(qr[i][2])if qr[i][1] not in d:d[qr[i][1]] = []d[qr[i][1]].append(qr[i][2])elif qr[i][0] == 2:qr[i][1] = int(qr[i][1])tm.append(qr[i][1])else:qr[i][2] = int(qr[i][2])qr[i][3] = int(qr[i][3])tm.append(qr[i][2])tm.append(qr[i][3])if qr[i][1] not in d:d[qr[i][1]] = []d[qr[i][1]].append(qr[i][2])d[qr[i][1]].append(qr[i][3])tm = list(set(tm))idx = cc(tm)st = segt(len(idx)+1, 0, add)idx2 = dict()sd = dict()for s in d.keys():idx2[s] = cc(list(set(d[s])))sd[s] = segt(len(idx2[s])+1, 0, add)for s, l, r in ls:st.renew(idx[l], 1)st.renew(idx[r]+1, -1)sd[s].renew(idx2[s][l], 1)sd[s].renew(idx2[s][r]+1, -1)for i in range(q):if qr[i][0] == 1:flg = sd[qr[i][1]].prod(0, idx2[qr[i][1]][qr[i][2]]+1)print("Yes" if flg else "No")elif qr[i][0] == 2:ans = st.prod(0, idx[qr[i][1]]+1)print(ans)else:s, l, r = qr[i][1:]st.renew(idx[l], 1)st.renew(idx[r]+1, -1)sd[s].renew(idx2[s][l], 1)sd[s].renew(idx2[s][r]+1, -1)