結果
問題 |
No.2716 Falcon Method
|
ユーザー |
![]() |
提出日時 | 2024-04-11 01:21:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 381 ms / 2,000 ms |
コード長 | 1,052 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 114,944 KB |
最終ジャッジ日時 | 2024-10-02 21:08:48 |
合計ジャッジ時間 | 6,938 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
from bisect import bisect_left N, Q = map(int, input().split()) S = input() HWP = [list(map(int, input().split())) for _ in range(Q)] cumD = [0] cumR = [0] for i in range(N): if S[i] == "D": cumD.append(cumD[-1]+1) cumR.append(cumR[-1]) else: cumD.append(cumD[-1]) cumR.append(cumR[-1]+1) for i in range(Q): H, W, P = HWP[i] if cumD[-1]-cumD[P] < H and cumR[-1]-cumR[P] < W: h, w = cumD[-1]-cumD[P], cumR[-1]-cumR[P] if cumD[-1] != 0 and cumR[-1] != 0: C = min((H-h-1)//cumD[-1], (W-w-1)//cumR[-1]) elif cumD[-1] != 0: C = (H-h-1)//cumD[-1] else: C = (W-w-1)//cumR[-1] h += cumD[-1]*C w += cumR[-1]*C H -= h W -= w P = 0 if cumD[-1]-cumD[P] >= H and cumR[-1]-cumR[P] >= W: print(min(bisect_left(cumD, cumD[P]+H), bisect_left(cumR, cumR[P]+W)) % N) elif cumD[-1]-cumD[P] >= H: print(bisect_left(cumD, cumD[P]+H)%N) else: print(bisect_left(cumR, cumR[P]+W)%N)