結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | 👑 Kazun |
提出日時 | 2022-02-11 20:44:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 806 ms / 3,000 ms |
コード長 | 6,699 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 82,548 KB |
実行使用メモリ | 140,288 KB |
最終ジャッジ日時 | 2024-04-17 12:30:27 |
合計ジャッジ時間 | 18,625 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
53,376 KB |
testcase_01 | AC | 38 ms
53,120 KB |
testcase_02 | AC | 51 ms
72,448 KB |
testcase_03 | AC | 318 ms
103,736 KB |
testcase_04 | AC | 339 ms
99,456 KB |
testcase_05 | AC | 345 ms
98,432 KB |
testcase_06 | AC | 470 ms
113,184 KB |
testcase_07 | AC | 547 ms
114,560 KB |
testcase_08 | AC | 347 ms
102,912 KB |
testcase_09 | AC | 451 ms
114,816 KB |
testcase_10 | AC | 432 ms
104,664 KB |
testcase_11 | AC | 292 ms
93,440 KB |
testcase_12 | AC | 436 ms
105,344 KB |
testcase_13 | AC | 255 ms
91,520 KB |
testcase_14 | AC | 341 ms
98,560 KB |
testcase_15 | AC | 267 ms
91,904 KB |
testcase_16 | AC | 429 ms
106,368 KB |
testcase_17 | AC | 676 ms
124,032 KB |
testcase_18 | AC | 604 ms
120,704 KB |
testcase_19 | AC | 690 ms
125,184 KB |
testcase_20 | AC | 176 ms
94,172 KB |
testcase_21 | AC | 263 ms
102,528 KB |
testcase_22 | AC | 300 ms
94,336 KB |
testcase_23 | AC | 227 ms
94,880 KB |
testcase_24 | AC | 269 ms
91,264 KB |
testcase_25 | AC | 580 ms
112,868 KB |
testcase_26 | AC | 595 ms
119,296 KB |
testcase_27 | AC | 182 ms
84,864 KB |
testcase_28 | AC | 288 ms
107,520 KB |
testcase_29 | AC | 535 ms
132,788 KB |
testcase_30 | AC | 353 ms
130,544 KB |
testcase_31 | AC | 323 ms
107,468 KB |
testcase_32 | AC | 806 ms
134,600 KB |
testcase_33 | AC | 756 ms
140,288 KB |
testcase_34 | AC | 669 ms
138,240 KB |
ソースコード
class Fenwick_Tree: def __init__(self, N, A=None): self.N=N if A==None: self.data=[0]*N else: assert len(A)==N self.data=A self.__build() def __build(self): data=self.data for i in range(1, self.N+1): if i+(i&(-i))<=self.N: data[i+(i&(-i))-1]+=data[i-1] def add(self, i, x): i+=1 data=self.data while i<=self.N: data[i-1]+=x i+=i&(-i) def sum(self, i): S=0 data=self.data while i: S+=data[i-1] i-=i&(-i) return S def range_sum(self,l,r): return self.sum(r)-self.sum(l) def bisect_left(self, x, default=-1): i=0 k=1<<self.N.bit_length() data=self.data while k: if i+k<=self.N and data[i+k-1]<x: x-=self.data[i+k-1] i+=k k>>=1 return i if x else default def bisect_right(self, x, default=-1): i=0 k=1<<self.N.bit_length() data=self.data while k: if i+k<=self.N and data[i+k-1]<=x: x-=self.data[i+k-1] i+=k k>>=1 return i if i<self.N else default class Ordered_Set: def __init__(self, N, multiple=False, S=None): self.N=N self.multiple=bool(multiple) if (not multiple) and S: S=[1 if S[i] else 0 for i in range(N)] self.Fenwick=Fenwick_Tree(N,S) self.__card=self.Fenwick.sum(N) def __contains__(self, x): return bool(self.count(x)) def count(self, x): return self.Fenwick.range_sum(x,x+1) def __len__(self): return self.__card def __bool__(self): return bool(len(self)) def add(self, x, k=1): """ x を k 個 (多重集合のとき) 加える. """ if (not self.multiple) and (x in self): return if not self.multiple: k=1 self.Fenwick.add(x,k) self.__card+=k def discard(self, x, k=1): """ x を k 個 (多重集合のとき) 削除する. x: int k: k=-1 とすると, x を全て削除する. """ if x not in self: return if k==-1: k=self.count(x) elif not self.multiple: k=1 self.Fenwick.add(x,-k) self.__card-=k def remove(self, x): """ x を k 個 (多重集合のとき) 削除する. x: int k: k=-1 とすると, x を全て削除する. """ if x not in self: raise KeyError(x) if k==-1: k=self.count(x) elif not self.multiple: k=1 self.Fenwick.add(x, -k) self.__card-=k def get(self, index, default=-1): size=len(self) if size<=index or size+index<0: return default if index<0: index+=size return self.Fenwick.bisect_left(index+1) def __getitem__(self, index): size=len(self) if size<=index or size+index<0: raise IndexError if index<0: index+=size return self.Fenwick.bisect_left(index+1) def get_min(self, default=-1): return self.get(0, default) def pop_min(self): y=self.get_min() if y==-1: raise IndexError self.remove(y) return y def get_max(self, default=-1): return self.get(-1, default) def pop_max(self): y=self.get_max() if y==-1: raise IndexError self.remove(y) return y def index(self, x, mode=False, default=-1): """ S[k]=x を満たす k を求める. x: int mode: False のときは k の最小値, True の時は k の最大値 (多重集合のとき有用) """ if x not in self: return default if mode: return self.Fenwick.sum(x+1)-1 else: return self.Fenwick.sum(x) def previous(self, x, mode=True, default=-1): """ S に含まれる x 以下の要素のうち, 最大値を求める. x: int mode: False のときは "以下" が "未満" になる. """ if mode: x+=1 if x>=0: return self.Fenwick.bisect_left(self.Fenwick.sum(x), default) else: return default def next(self, x, mode=True, default=-1): """ S に含まれる x 以上の要素のうち, 最大値を求める. x: int mode: False のときは "以上" が "より大きい" になる. """ if not mode: x+=1 return self.Fenwick.bisect_right(self.Fenwick.sum(x), default) def less_count(self, x, mode=False): """ x 未満の元の個数を求める. x: int mode: mode=True ならば, "未満" が "以下" になる. """ if mode: x+=1 return self.Fenwick.sum(x) def more_count(self, x, mode=False): """ x より大きい元の個数を求める. x: int mode: mode=True ならば, "より大きい" が "以上" になる. """ return len(self)-self.less_count(x, not mode) def kth_min(self, k, default=-1): """ k 番目に小さい元を求める. """ if 1<=k<=len(self): return self[k-1] else: return default def kth_max(self, k, default=-1): """ k 番目に大きい元を求める. """ if 1<=k<=len(self): return self[~(k-1)] else: return default #================================================== import sys input=sys.stdin.readline write=sys.stdout.write N,K,Q=map(int,input().split()) C=[0]*K D=[[] for _ in range(N+2)] for k in range(K): L,R,C[k],M=map(int,input().split()) D[L].append((k,M)) D[R+1].append((k,-M)) Quest=[[] for _ in range(N+2)] for q in range(Q): I,X=map(int,input().split()) Quest[I].append((q,X)) Ans=[0]*Q S=Ordered_Set(K,True) for n in range(1,N+1): for k,h in D[n]: S.add(k,h) for q,x in Quest[n]: if x<=len(S): Ans[q]=C[S[x-1]] else: Ans[q]=-1 write("\n".join(map(str,Ans)))