觀光旅遊 (APCS 2026-03 中高級)
2.0s 256M有 \(n\) 位旅客,各在指定日期抵達。第 \(j\) 個行程可讓抵達日落在閉區間 \([s_j,e_j]\) 的旅客參加。每位旅客與每個符合條件的行程各形成一組配對;請計算配對總數。相同日期的旅客仍分別計算。
輸入格式
第一行為 \(n,m\)。第二行為 \(n\) 個抵達日。接著 \(m\) 行各為一個行程的 \(s_j,e_j\)。
限制
\(1\le n,m\le10^5\);所有日期介於 \(1\) 與 \(10^8\),且 \(s_j\le e_j\)。
輸出格式
輸出配對總數。
評分說明
每筆計分測資獨立計分,每筆 5 分,共 100 分;範例不計分。
- 1: 40% — \(n,m\le1000\)
- 2: 60% — 無額外限制。
範例輸入
3 5
7 5 10
2 5
3 9
7 8
4 6
5 6
範例輸出
6
題目來源
APCS 2026 年 3 月中高級實作題第 2 題。
題敘參考 ZeroJudge s180「觀光旅遊」 整理,細節可能與正式試題有出入。