#1181658 (C++23(gcc16)) No.3667 Prefix Count Queries

• 問題: No.3667 Prefix Count Queries
• ユーザー: Rino-program
• 提出日時: 2026-08-30 20:49:02
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 30 ms / 2,000 ms
• コード長: 4,093 bytes
• コンパイル時間: 820 ms
• コンパイル使用メモリ: 95,644 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2026-09-01 00:51:24
• 合計ジャッジ時間: 5,552 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

// 高速入出力用バッファ (最大ケース約 10MB に対応)
static char in_buf[16 * 1024 * 1024];
static char out_buf[8 * 1024 * 1024];
static int in_pos = 0;
static int out_pos = 0;

inline void skip_spaces() {
    while (in_buf[in_pos] <= ' ' && in_buf[in_pos] != '\0') {
        in_pos++;
    }
}

inline int read_int() {
    skip_spaces();
    int x = 0;
    while (in_buf[in_pos] >= '0' && in_buf[in_pos] <= '9') {
        x = x * 10 + (in_buf[in_pos++] - '0');
    }
    return x;
}

struct StrInfo {
    const char* ptr;
    int len;
};

// インライン文字列読み取り（ゼロコピー）
inline StrInfo read_str() {
    skip_spaces();
    const char* start = &in_buf[in_pos];
    while (static_cast<unsigned char>(in_buf[in_pos]) > ' ') {
        in_pos++;
    }
    int len = (int)(&in_buf[in_pos] - start);
    in_buf[in_pos++] = '\0'; // 終端を \0 に置換
    return {start, len};
}

inline void write_uint(int x) {
    if (x == 0) {
        out_buf[out_pos++] = '0';
        out_buf[out_pos++] = '\n';
        return;
    }
    char temp[12];
    int p = 0;
    while (x > 0) {
        temp[p++] = (x % 10) + '0';
        x /= 10;
    }
    while (p > 0) {
        out_buf[out_pos++] = temp[--p];
    }
    out_buf[out_pos++] = '\n';
}

struct Range {
    int L, R;
};

static StrInfo items[200005];
static Range stack_range[200005];

int main() {
    // 入力を一括でバッファに読み込む
    fread(in_buf, 1, sizeof(in_buf), stdin);

    int N = read_int();
    for (int i = 0; i < N; ++i) {
        items[i] = read_str();
    }

    // 辞書順に高速ソート
    sort(items, items + N, [](const StrInfo& a, const StrInfo& b) {
        return strcmp(a.ptr, b.ptr) < 0;
    });

    int Q = read_int();

    int sp = 0;
    stack_range[0] = {0, N};

    // d 文字目を返す（長さ不足時は 0 を返すことで常にターゲット文字より小さい扱いにする）
    auto get_char = [](int idx, int d) -> int {
        return (d < items[idx].len) ? static_cast<unsigned char>(items[idx].ptr[d]) : 0;
    };

    while (Q--) {
        skip_spaces();
        char type = in_buf[in_pos++];

        if (type == '1') {
            skip_spaces();
            char x = in_buf[in_pos++];
            Range cur = stack_range[sp];
            int d = sp; // 現在追加する文字の深さ

            if (cur.L >= cur.R) {
                stack_range[++sp] = {0, 0};
            } else {
                int target = static_cast<unsigned char>(x);

                // lower_bound: target 以上の最初の位置
                int l1 = cur.L;
                int count1 = cur.R - cur.L;
                while (count1 > 0) {
                    int step = count1 >> 1;
                    int mid = l1 + step;
                    if (get_char(mid, d) < target) {
                        l1 = mid + 1;
                        count1 -= step + 1;
                    } else {
                        count1 = step;
                    }
                }
                int new_L = l1;

                // upper_bound: target より大きい最初の位置
                int l2 = new_L;
                int count2 = cur.R - new_L;
                while (count2 > 0) {
                    int step = count2 >> 1;
                    int mid = l2 + step;
                    if (get_char(mid, d) <= target) {
                        l2 = mid + 1;
                        count2 -= step + 1;
                    } else {
                        count2 = step;
                    }
                }
                int new_R = l2;

                stack_range[++sp] = {new_L, new_R};
            }
        } else if (type == '2') {
            sp--;
        } else if (type == '3') {
            write_uint(stack_range[sp].R - stack_range[sp].L);
        }
    }

    // 出力を一括書き出し
    fwrite(out_buf, 1, out_pos, stdout);

    return 0;
}