結果

問題 No.3667 Prefix Count Queries
ユーザー Rino-program
提出日時 2026-10-02 21:53:26
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 50 ms / 2,000 ms
+ 690µs
コード長 2,719 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,227 ms
コンパイル使用メモリ 206,752 KB
実行使用メモリ 10,352 KB
最終ジャッジ日時 2026-10-02 21:53:37
合計ジャッジ時間 6,343 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// S の長さに応じた A のインデックス範囲 [L, R) を管理する構造体
struct Range {
    int l, r;
};

int main() {
    // 高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    vector<string> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // A を辞書順にソート
    sort(A.begin(), A.end());

    int Q;
    cin >> Q;

    // 現在の各文字長における有効な範囲 [L, R) をスタックで管理
    // 初期状態（長さ 0 のとき）は全体 [0, N)
    vector<Range> history;
    history.push_back({0, N});

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            char x;
            cin >> x;
            
            // 現在の S の長さ（次に見るべき文字のインデックス）
            int k = (int)history.size() - 1;
            auto [cur_l, cur_r] = history.back();

            if (cur_l >= cur_r) {
                // 既に一致するものが 0 個なら、文字を追加しても 0 個のまま
                history.push_back({cur_l, cur_r});
                continue;
            }

            // k 文字目が x 以上の最初の位置を二分探索
            // ※ A[i] の長さが k 以下の場合は x より小さい文字（空文字）とみなす
            int new_l = cur_l;
            {
                int ok = cur_r, ng = cur_l - 1;
                while (ok - ng > 1) {
                    int mid = ng + (ok - ng) / 2;
                    char c = (A[mid].length() > k) ? A[mid][k] : 0;
                    if (c >= x) ok = mid;
                    else ng = mid;
                }
                new_l = ok;
            }

            // k 文字目が x 超の最初の位置を二分探索
            int new_r = cur_r;
            {
                int ok = cur_r, ng = cur_l - 1;
                while (ok - ng > 1) {
                    int mid = ng + (ok - ng) / 2;
                    char c = (A[mid].length() > k) ? A[mid][k] : 0;
                    if (c > x) ok = mid;
                    else ng = mid;
                }
                new_r = ok;
            }

            history.push_back({new_l, new_r});

        } else if (type == 2) {
            // 末尾を削除するので、直前の範囲に戻すだけ
            history.pop_back();

        } else if (type == 3) {
            // 現在の範囲の要素数を出力するだけ
            auto [cur_l, cur_r] = history.back();
            cout << (cur_r - cur_l) << "\n";
        }
    }

    return 0;
}
0