#1084042 (C++17) No.3016 ハチマキおじさん

• 問題: No.3016 ハチマキおじさん
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:15:40
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: RE
• 実行時間: -
• コード長: 6,044 bytes
• コンパイル時間: 820 ms
• コンパイル使用メモリ: 66,224 KB
• 実行使用メモリ: 8,832 KB
• 最終ジャッジ日時: 2025-05-14 13:16:56
• 合計ジャッジ時間: 4,425 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	WA * 26 RE * 5

ソースコード

#include <cstdio>       // For scanf, printf (often faster than C++ iostreams)
#include <vector>       // For std::vector container
#include <algorithm>    // For std::sort

// Define a structure to hold the values from array B and their original indices.
// This is needed because we will sort B based on values, but need to output
// the counts in the original order.
struct Query {
    long long value;      // The value from array B
    int original_index; // The original index (0 to M-1) of this value in B
};

// Custom comparison function used to sort the Query structs based on their 'value' field.
// This is passed as the third argument to std::sort.
bool compareQueries(const Query& a, const Query& b) {
    // Sort primarily based on the 'value'. The relative order of queries with the same value
    // doesn't impact correctness, as std::sort is stable or we process them together anyway.
    return a.value < b.value;
}

int main() {
    int N, M;
    // Read the sizes of arrays A and B.
    // Using scanf is generally preferred in competitive programming for speed.
    // Basic error checking on scanf return value is good practice.
    if (scanf("%d %d", &N, &M) != 2) {
        // Handle potential input error (though often omitted in contests)
        return 1; 
    }

    // Use std::vector for dynamic arrays. It's safer and more convenient than raw arrays.
    // Initialize vector A with size N to avoid potential reallocations during input reading.
    std::vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        // Read each element of A. Use %lld format specifier for long long.
        if (scanf("%lld", &A[i]) != 1) {
             return 1; // Handle input error
        }
    }

    // Read the elements of B and store them along with their original indices
    // in a vector of Query structs. Initialize with size M.
    std::vector<Query> B_indexed(M);
    for (int i = 0; i < M; ++i) {
        // Read the value B_i
        if (scanf("%lld", &B_indexed[i].value) != 1) {
            return 1; // Handle input error
        }
        // Store its original index i
        B_indexed[i].original_index = i;
    }

    // Sort array A in non-decreasing order. This is crucial for the efficient counting step.
    // std::sort has an average time complexity of O(N log N).
    std::sort(A.begin(), A.end());

    // Sort the vector of queries (B_indexed) based on their 'value' field.
    // We use the custom comparison function `compareQueries`.
    // This groups identical query values together, allowing us to process them efficiently.
    // Time complexity is O(M log M).
    std::sort(B_indexed.begin(), B_indexed.end(), compareQueries);

    // Create the result vector C of size M to store the counts.
    // std::vector<int> initializes elements to 0 by default.
    std::vector<int> C(M); 

    int idxA = 0; // Pointer (index) for iterating through the sorted array A.
    int idxB = 0; // Pointer (index) for iterating through the sorted array B_indexed.

    // Implement the two-pointer (or coordinate compression / sweep-line style) approach.
    // Iterate through the sorted queries (B_indexed).
    while (idxB < M) {
        // Get the target value for the current block of queries.
        long long current_target_value = B_indexed[idxB].value;

        // Phase 1: Advance the pointer idxA in array A.
        // Move idxA forward as long as the element A[idxA] is strictly less than the target value.
        // This efficiently skips elements in A that are smaller than the current query value.
        while (idxA < N && A[idxA] < current_target_value) {
            idxA++;
        }
        // After this loop, either idxA == N (we reached the end of A)
        // or A[idxA] >= current_target_value.

        // Phase 2: Count occurrences of current_target_value in A.
        int count = 0; // Initialize count for this target value.
        // Check if we are within the bounds of A and if the element at idxA matches the target value.
        if (idxA < N && A[idxA] == current_target_value) {
            // If found, count all consecutive occurrences of this value starting from idxA.
            int start_idxA = idxA; // Remember the starting index of this sequence.
            // Keep advancing idxA as long as we see the target value.
            while (idxA < N && A[idxA] == current_target_value) {
                idxA++;
            }
            // The number of occurrences is the difference between the final and starting indices.
            count = idxA - start_idxA;
            // Importantly, after counting, idxA is already positioned correctly
            // for the search of the *next distinct* target value. It points to the
            // first element strictly greater than current_target_value (or N).
        }
        // If the target value was not found (A[idxA] > current_target_value or idxA == N),
        // the count remains 0.

        // Phase 3: Assign the computed count to all queries in B_indexed that have this target value.
        // Since B_indexed is sorted by value, all queries for current_target_value form a contiguous block.
        // Iterate through this block.
        while (idxB < M && B_indexed[idxB].value == current_target_value) {
            // Use the stored original_index to place the count in the correct position in the result vector C.
            C[B_indexed[idxB].original_index] = count;
            // Move to the next query in B_indexed.
            idxB++;
        }
        // After this loop, idxB points to the first query with a value greater than
        // current_target_value (or idxB == M), ready for the next iteration of the outer while loop.
    }

    // Print the final counts stored in vector C.
    for (int i = 0; i < M; ++i) {
        // Print each count followed by a space, except for the last count,
        // which should be followed by a newline character.
        printf("%d%c", C[i], (i == M - 1) ? '\n' : ' ');
    }

    return 0; // Indicate successful execution.
}