Hướng dẫn giải của Phát quà (KS3)
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ỗi lượt phát quà là một đoạn ~[L, R]~. Với mỗi học sinh ~x~, số gói quà nhận được là số đoạn chứa ~x~.
Sub 1: vét cạn — ~O(k \cdot Q)~, dùng khi ~k \cdot Q \le 10^7~
Với mỗi câu hỏi, duyệt hết ~k~ đoạn và đếm đoạn chứa ~x~. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: đếm bằng sắp xếp — ~O((k+Q) \log k)~
Số đoạn chứa ~x~ bằng (số ~L \le x~) trừ (số ~R < x~). Vì mỗi đoạn có ~L \le R~, đoạn có ~R < x~ chắc chắn có ~L < x~. Sắp xếp ~L~ và ~R~ rồi dùng tìm nhị phân. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc n, k, Q và các đoạn. Nếu ~k \cdot Q \le 10^7~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, k, Q;
vector<long long> L, R, X;
// Sub 1: vét cạn, với mỗi học sinh hỏi duyệt hết k lượt phát quà. O(k*Q)
void sub1() {
for (long long q = 0; q < Q; q++) {
long long cnt = 0;
for (long long i = 0; i < k; i++)
if (L[i] <= X[q] && X[q] <= R[i]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: đếm số đoạn [L,R] chứa x = (số L <= x) - (số R < x). O((k+Q) log k)
void sub2() {
vector<long long> sl = L, sr = R;
sort(sl.begin(), sl.end());
sort(sr.begin(), sr.end());
for (long long q = 0; q < Q; q++) {
long long x = X[q];
long long a = upper_bound(sl.begin(), sl.end(), x) - sl.begin(); // L <= x
long long b = lower_bound(sr.begin(), sr.end(), x) - sr.begin(); // R < x
cout << a - b << "\n";
}
}
int main() {
freopen("GIFTS.INP", "r", stdin);
freopen("GIFTS.OUT", "w", stdout);
cin >> n >> k >> Q;
L.resize(k); R.resize(k); X.resize(Q);
for (long long i = 0; i < k; i++) cin >> L[i] >> R[i];
for (long long q = 0; q < Q; q++) cin >> X[q];
if (k * Q <= 10000000LL) sub1();
else sub2();
return 0;
}
Bình luận