結果

問題 No.2716 Falcon Method
ユーザー june19312
提出日時 2024-04-05 23:16:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 734 ms / 2,000 ms
コード長 3,304 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 103,524 KB
最終ジャッジ日時 2024-10-01 03:04:43
合計ジャッジ時間 11,521 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#=======mybisect==========

from bisect import *
def mybisect(x,y):
    """
    x = 値
    y = 配列
    配列と値が与えられた際に、以下、以上、未満、超のそれぞれについて
    個数、開始インデックス、終了インデックスとその値を返す
    """
    #返す値を減らしたいとき、ここから下は適宜削除可能

    lt = bisect_left(y,x)
    le = bisect_right(y,x)
    ge = len(y)-lt
    gt = len(y)-le

    lt_ind_s_val,lt_ind_e_val = -1,-1
    le_ind_s_val,le_ind_e_val = -1,-1
    ge_ind_s_val,ge_ind_e_val = -1,-1
    gt_ind_s_val,gt_ind_e_val = -1,-1

    if lt > 0:
        lt_ind_s,lt_ind_e = 0,lt-1
        lt_ind_s_val,lt_ind_e_val = y[lt_ind_s],y[lt_ind_e]
    else:
        lt_ind_s,lt_ind_e = None,None

    if le > 0:
        le_ind_s,le_ind_e = 0,le-1
        le_ind_s_val,le_ind_e_val = y[le_ind_s],y[le_ind_e]
    else:
        le_ind_s,le_ind_e = None,None

    if ge > 0:
        ge_ind_s,ge_ind_e = lt,len(y)-1
        ge_ind_s_val,ge_ind_e_val = y[lt],y[len(y)-1]
    else:
        ge_ind_s,ge_ind_e = None,None

    if gt > 0:
        gt_ind_s,gt_ind_e = le,len(y)-1
        gt_ind_s_val,gt_ind_e_val = y[gt_ind_s],y[gt_ind_e]
    else:
        gt_ind_s,gt_ind_e = None,None

#            0    1  2      3        4            5        6            7        8            9
    return len(y),lt,ge,lt_ind_s,lt_ind_s_val,lt_ind_e,lt_ind_e_val,ge_ind_s,ge_ind_s_val,ge_ind_e,ge_ind_e_val,le,gt,le_ind_s,le_ind_s_val,le_ind_e,le_ind_e_val,gt_ind_s,gt_ind_s_val,gt_ind_e,gt_ind_e_val

#=======mybisectここまで==========

N,Q = map(int,input().split())
S = input()
r,d = [0],[0]

for i,v in enumerate(S):
        if v == "R":
            r.append(r[-1]+1)
            d.append(d[-1])
        else:
            r.append(r[-1])
            d.append(d[-1]+1)

#print("d",d)
#print("r",r)

for i in range(Q):
    D,R,P = map(int,input().split())

    #1週目でrとdがいくつ増えるか
    first_d = d[-1] - d[P]
    first_r = r[-1] - r[P]

#    print("first_d",first_d,"first_r",first_r)

    if D <= first_d and R <= first_r:
        tmpD = mybisect(d[P]+D,d)[7]
        tmpR = mybisect(r[P]+R,r)[7]
        print(min(tmpD,tmpR)%N) #ans
        continue
    elif D <= first_d and first_r < R:
        tmpD = mybisect(d[P]+D,d)[7]%N
        print(tmpD) #ans
        continue
    elif first_d < D and R <= first_r:
        tmpR = mybisect(r[P]+R,r)[7]%N
        print(tmpR) #ans
        continue

    if  d[-1] != 0 and (D-first_d)%d[-1] == 0:
        tmpD2 = (D-first_d)//d[-1]
    elif d[-1] != 0:
        tmpD2 = (D-first_d)//d[-1]+1
    else:
        tmpD2 = 10**100

    if r[-1] != 0 and (R-first_r)%r[-1] == 0:
        tmpR2 = (R-first_r)//r[-1]
    elif r[-1] != 0:
        tmpR2 = (R-first_r)//r[-1]+1
    else:
        tmpR2 = 10**100

#    print("tmpD2",tmpD2,"tmpR2",tmpR2)
    nokoriD = (D-first_d)-(d[-1]*(tmpD2-1))
    nokoriR = (R-first_r)-(r[-1]*(tmpR2-1))

#    print("nokoriD",nokoriD,"nokoriR",nokoriR)
#    print()
    if tmpD2 < tmpR2:
        print(mybisect(nokoriD,d)[7]%N) #ans
    elif tmpD2 > tmpR2:
        print(mybisect(nokoriR,r)[7]%N) #ans
    else:
        aa = mybisect(nokoriD,d)[7]
        bb = mybisect(nokoriR,r)[7]
#        print("aa",aa,"bb",bb)
        print(min(aa,bb)%N) #ans
0