結果

問題 No.1471 Sort Queries
コンテスト
ユーザー ygd.
提出日時 2021-04-09 23:26:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 965 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 312 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 84,616 KB
最終ジャッジ日時 2024-06-25 07:23:58
合計ジャッジ時間 18,953 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

N,Q = map(int,input().split())
S = str(input())
SL = []
for i in range(N):
    SL.append(ord(S[i])-96) #1index
#print(SL)
for i in range(Q):
    l,r,x = map(int,input().split())
    l-=1;r-=1
    Tree = BIT(28)
    for j in range(l,r+1):
        num = SL[j]
        Tree.add(num,1)
    if Tree.get(1,1) >= x:
        print("a")
        continue
    ok = 28
    ng = 1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if Tree.get(1,mid) >= x:
            ok = mid
        else:
            ng = mid
    #print(ok)
    ans = chr(ok+96)
    print(ans)
0