結果

問題 No.2716 Falcon Method
コンテスト
ユーザー InTheBloom
提出日時 2026-01-23 23:02:41
言語 D
(dmd 2.111.0)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 1,507 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,169 ms
コンパイル使用メモリ 195,608 KB
実行使用メモリ 131,052 KB
最終ジャッジ日時 2026-01-23 23:02:55
合計ジャッジ時間 13,274 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std;

void main () {
    int N, Q;
    readln.read(N, Q);
    string S = readln.chomp;

    auto H = new int[](Q);
    auto W = new int[](Q);
    auto P = new int[](Q);
    foreach (i; 0 .. Q) {
        readln.read(H[i], W[i], P[i]);
    }

    auto p = new int[][](31, N);
    auto dp = new Tuple!(long, long)[][](31, N);
    foreach (bit; 0 .. 31) {
        foreach (i; 0 .. N) {
            if (bit == 0) {
                dp[bit][i] = (S[i] == 'D' ? tuple(1L, 0L) : tuple(0L, 1L));
                p[bit][i] = (i + 1) % N;
            }
            else {
                p[bit][i] = p[bit - 1][p[bit - 1][i]];
                auto pr = dp[bit - 1][i];
                auto su = dp[bit - 1][p[bit - 1][i]];
                pr[0] += su[0];
                pr[1] += su[1];
                dp[bit][i] = pr;
            }
        }
    }

    auto ans = new int[](Q);
    foreach (i; 0 .. Q) {
        int cur = P[i];
        auto val = tuple(0L, 0L);
        foreach_reverse (bit; 0 .. 31) {
            if (val[0] + dp[bit][cur][0] < H[i] && val[1] + dp[bit][cur][1] < W[i]) {
                val[0] += dp[bit][cur][0];
                val[1] += dp[bit][cur][1];
                cur = p[bit][cur];
            }
        }

        ans[i] = (cur + 1) % N;
    }

    writefln("%(%s\n%)", ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0