結果
問題 | No.2716 Falcon Method |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#=======mybisect==========from bisect import *def mybisect(x,y):"""x = 値y = 配列配列と値が与えられた際に、以下、以上、未満、超のそれぞれについて個数、開始インデックス、終了インデックスとその値を返す"""#返す値を減らしたいとき、ここから下は適宜削除可能lt = bisect_left(y,x)le = bisect_right(y,x)ge = len(y)-ltgt = len(y)-lelt_ind_s_val,lt_ind_e_val = -1,-1le_ind_s_val,le_ind_e_val = -1,-1ge_ind_s_val,ge_ind_e_val = -1,-1gt_ind_s_val,gt_ind_e_val = -1,-1if lt > 0:lt_ind_s,lt_ind_e = 0,lt-1lt_ind_s_val,lt_ind_e_val = y[lt_ind_s],y[lt_ind_e]else:lt_ind_s,lt_ind_e = None,Noneif le > 0:le_ind_s,le_ind_e = 0,le-1le_ind_s_val,le_ind_e_val = y[le_ind_s],y[le_ind_e]else:le_ind_s,le_ind_e = None,Noneif ge > 0:ge_ind_s,ge_ind_e = lt,len(y)-1ge_ind_s_val,ge_ind_e_val = y[lt],y[len(y)-1]else:ge_ind_s,ge_ind_e = None,Noneif gt > 0:gt_ind_s,gt_ind_e = le,len(y)-1gt_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 9return 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) #anscontinueelif D <= first_d and first_r < R:tmpD = mybisect(d[P]+D,d)[7]%Nprint(tmpD) #anscontinueelif first_d < D and R <= first_r:tmpR = mybisect(r[P]+R,r)[7]%Nprint(tmpR) #anscontinueif 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]+1else:tmpD2 = 10**100if 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]+1else: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) #anselif tmpD2 > tmpR2:print(mybisect(nokoriR,r)[7]%N) #anselse:aa = mybisect(nokoriD,d)[7]bb = mybisect(nokoriR,r)[7]# print("aa",aa,"bb",bb)print(min(aa,bb)%N) #ans