結果
問題 | No.1471 Sort Queries |
ユーザー |
![]() |
提出日時 | 2021-04-09 21:36:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 824 bytes |
コンパイル時間 | 415 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 79,488 KB |
最終ジャッジ日時 | 2024-06-25 04:31:45 |
合計ジャッジ時間 | 4,673 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
""" """ import sys from sys import stdin alp = "abcdefghijklmnopqrstuvwxyz" def bitadd(a,w,bit): #aにwを加える(1-origin) a += 1 x = a while x <= (len(bit)-1): bit[x] += w x += x & (-1 * x) def bitsum(a,bit): #ind 1~aまでの和を求める a += 1 ret = 0 x = a while x > 0: ret += bit[x] x -= x & (-1 * x) return ret ans = [] N,Q = map(int,stdin.readline().split()) S = stdin.readline()[:-1] b = [[0] * (N+5) for i in range(26)] for i in range(1,N+1): c = ord(S[i-1])-ord('a') bitadd(i,1,b[c]) for loop in range(Q): L,R,X = map(int,stdin.readline().split()) for i in range(26): X -= bitsum(R,b[i]) - bitsum(L-1,b[i]) if X <= 0: ans.append(alp[i]) break print ("\n".join(ans))