結果

問題 No.2716 Falcon Method
ユーザー june19312june19312
提出日時 2024-04-05 23:16:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 844 ms / 2,000 ms
コード長 3,304 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 103,180 KB
最終ジャッジ日時 2024-04-05 23:16:17
合計ジャッジ時間 12,525 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,460 KB
testcase_01 AC 38 ms
53,460 KB
testcase_02 AC 37 ms
53,460 KB
testcase_03 AC 38 ms
53,460 KB
testcase_04 AC 37 ms
53,460 KB
testcase_05 AC 38 ms
53,460 KB
testcase_06 AC 77 ms
72,384 KB
testcase_07 AC 80 ms
72,764 KB
testcase_08 AC 78 ms
73,020 KB
testcase_09 AC 74 ms
72,508 KB
testcase_10 AC 74 ms
72,384 KB
testcase_11 AC 508 ms
103,008 KB
testcase_12 AC 611 ms
99,560 KB
testcase_13 AC 466 ms
99,560 KB
testcase_14 AC 800 ms
96,820 KB
testcase_15 AC 614 ms
99,532 KB
testcase_16 AC 785 ms
96,784 KB
testcase_17 AC 658 ms
97,084 KB
testcase_18 AC 844 ms
99,404 KB
testcase_19 AC 624 ms
96,824 KB
testcase_20 AC 442 ms
99,552 KB
testcase_21 AC 454 ms
96,952 KB
testcase_22 AC 540 ms
103,180 KB
testcase_23 AC 450 ms
99,644 KB
testcase_24 AC 548 ms
103,180 KB
testcase_25 AC 36 ms
53,460 KB
testcase_26 AC 36 ms
53,460 KB
testcase_27 AC 646 ms
99,572 KB
testcase_28 AC 629 ms
99,580 KB
権限があれば一括ダウンロードができます

ソースコード

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