Overview

Putting all students on the “bus with the highest ceiling” is optimal, and the answer is the “number of students whose height exceeds the maximum ceiling height.”

Analysis

At first glance, this problem seems to have several complex conditions:

• Students in the same class must ride the same bus.
• There is no capacity limit for each bus.
• Students feel uncomfortable if their height is strictly greater than the ceiling height of the bus.

However, the fact that buses have no capacity limit is extremely important. Because of this, in the extreme case, we can put all students together on a single bus. If we put everyone on the same bus, the constraint “students in the same class must ride the same bus” is automatically satisfied.

So, which bus is the most advantageous to put everyone on?

Focusing on a student \(j\) (with height \(H_j\)), for this student not to feel uncomfortable, they must ride a bus \(i\) such that \(H_j \leq D_i\). In other words, buses with higher ceilings make fewer students uncomfortable.

Let \(D_{\max}\) be the maximum ceiling height among the \(N\) buses.

• If \(H_j \leq D_{\max}\), this student will not feel uncomfortable if put on the bus with the highest ceiling.
• If \(H_j > D_{\max}\), since there is no bus with a ceiling higher than \(D_{\max}\), this student will inevitably feel uncomfortable no matter which bus they ride.

Therefore, it is optimal to put all students on the bus with the highest ceiling. In this case, the only students who feel uncomfortable are those who satisfy \(H_j > D_{\max}\). Since it is impossible to reduce the number of uncomfortable students further (students with \(H_j > D_{\max}\) will feel uncomfortable no matter what we do), this is the minimum possible value.

In other words, the class information and the distribution of individual bus heights do not actually matter; we only need to count the number of students whose height exceeds the maximum ceiling height \(D_{\max}\).

Algorithm

1. Read the \(N\) ceiling heights \(D_i\) and find their maximum value \(D_{\max}\).
2. For the \(M\) students, read their height \(H_j\) and count the number of students such that \(H_j > D_{\max}\).
3. Output the count.

Since the class name \(S_j\) does not affect the answer, you can just skip reading it (because we can put everyone on the same bus, the constraint of grouping classes is always satisfied).

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(1)\) (excluding the input buffer)

Since we only scan the \(N\) buses once to find the maximum value, and then scan the \(M\) students once to count, it can be processed in linear time.

Implementation Details

• Since \(N\) can be up to \(10^6\), slow input reading might cause a TLE (Time Limit Exceeded). In the solution code, we can use fread to load the input at once and use a custom parser to process integers and strings quickly.

• Since the class name \(S_j\) is not used, it is sufficient to just skip the lowercase letters (like with a skipString function). There is no need to store the value.

• \(D_i\) and \(H_j\) are up to \(10^9\), so they fit in a standard 32-bit signed integer (int), but we can use 64-bit integers (long long) for safety. The maximum possible answer is \(M \leq 10^5\), which also fits well within standard integer types.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 高速入力
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    
    auto readInt = [&]() -> long long {
        while(pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if(pos < len && buf[pos] == '-'){ neg = true; pos++; }
        long long x = 0;
        while(pos < len && buf[pos] >= '0' && buf[pos] <= '9'){
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };
    auto skipString = [&](){
        // 空白をスキップして文字列(英小文字)を読み飛ばす
        while(pos < len && (buf[pos] == ' ' || buf[pos] == '\n' || buf[pos] == '\r' || buf[pos] == '\t')) pos++;
        while(pos < len && buf[pos] >= 'a' && buf[pos] <= 'z') pos++;
    };
    
    long long N = readInt();
    long long M = readInt();
    
    long long maxD = 0;
    for(long long i = 0; i < N; i++){
        long long d = readInt();
        if(d > maxD) maxD = d;
    }
    
    long long ans = 0;
    for(long long j = 0; j < M; j++){
        skipString();          // クラス名（不要）
        long long h = readInt();
        if(h > maxD) ans++;
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.