Hướng dẫn giải của [VTT Q4 Contest 02] Bài 3: Đoạn thẳng [LINE]
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số đoạn chứa ít nhất 2 điểm trong số ~m~ điểm. Mấu chốt là đếm nhanh số điểm nằm trong một đoạn.
Sub 1: Vét cạn — ~O(n \cdot m)~, dùng khi ~n, m \le 1000~
Với mỗi đoạn, duyệt mọi điểm và đếm điểm thỏa ~a_i \le p_j \le b_i~; nếu đếm được ít nhất 2 thì tăng kết quả. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Sắp xếp và chặt nhị phân — ~O((n+m) \log m)~
Sắp xếp các điểm tăng dần. Với đoạn ~[a_i, b_i]~, số điểm trong đoạn bằng (vị trí đầu tiên có ~p > b_i~) trừ (vị trí đầu tiên có ~p \ge a_i~), tìm bằng upper_bound và lower_bound. Đếm đoạn có hiệu này ít nhất 2. Chương trình đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu; nếu ~n \cdot m~ nhỏ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long A[100005], B[100005], p[100005];
// Sub 1: vét cạn ~O(n*m)~ — với mỗi đoạn đếm số điểm nằm trong nó
void sub1() {
int res = 0;
for (int i = 1; i <= n; i++) {
int c = 0;
for (int j = 1; j <= m; j++) if (A[i] <= p[j] && p[j] <= B[i]) c++;
if (c >= 2) res++;
}
cout << res;
}
// Sub 2: sắp xếp điểm, chặt nhị phân số điểm trong [a, b] — ~O((n+m) log m)~
void sub2() {
sort(p + 1, p + m + 1);
int res = 0;
for (int i = 1; i <= n; i++) {
int c = upper_bound(p + 1, p + m + 1, B[i]) - lower_bound(p + 1, p + m + 1, A[i]);
if (c >= 2) res++;
}
cout << res;
}
int main() {
freopen("LINE.INP", "r", stdin);
freopen("LINE.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> A[i] >> B[i];
for (int j = 1; j <= m; j++) cin >> p[j];
if ((long long)n * m <= 2000000) sub1();
else sub2();
}
Bình luận